Языки и трансляции. Мартыненко Б.К. - 128 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

127
Мы можем распространить подстановку f далее на языки, определяя .
Пример 9.1. Пусть f(0) = {a}, f (1) = {ww
R
|w∈{b, c}
*
}. Подстановка f
отображает
множество {0
n
1
n
|n ≥ 1} в {a
n
w
1
w
1
R
w
2
w
2
R
…w
n
w
n
R
|w
i
∈{b, c}
*
для
1 ≤ i ≤ n
}.
Говорят, что класс языков замкнут относительно подстановки, если для
любого языка L ⊆Σ
*
в данном классе и для любой подстановки f, такой, что
f(a) в данном классе для всех a∈Σ, язык f (L) содержится в этом же классе.
Покажем,
что классы регулярных множеств, контекстно-свободных языков и
языков
типа 0 замкнуты относительно подстановки.
Так, в примере 9.1, поскольку f (0) и f (1) — оба контекстно-свободные
языки и так как L =
{0
n
1
n
| n ≥ 1} — контекстно-свободный язык, то множество
f (L) = {a
n
w
1
w
1
R
w
2
w
2
R
…w
n
w
n
R
| w
i
∈{b, c}
*
для 1≤i ≤n} также контекстно-свобод-
ный язык.
Теорема 9.7. Классы регулярных множеств, контекстно-свободных
языков и языков типа 0 замкнуты относительно подстановки.
Доказательство. Рассмотрим грамматику G =(V
N
, {a
1
, a
2
,…, a
n
}, P, S).
Пусть G
i
=(V
N
i
, V
T
i
, P
i
, S
i
) — грамматика, порождающая множество f (a
i
) для
каждого i, 1 ≤ i ≤ n. Без потери общности предполагаем, что все нетерминаль-
ные словари попарно не пересекаются.
Докажем теорему для случая, когда грамматики G и G
i
, 1 ≤ i ≤ n , являются
контекстно-свободными. Читатель может доказать другие случаи аналогично,
хотя в каждом необходимы дополнительные детали.
Построим новую грамматику:
NT
(,,,),GVVPS
′′′
=
где
N
NT
T
N
11
= , = .
i
i
nn
ii
VV VV V
==
′′
∪
∪∪
Пусть h — подстановка h(a
i
)={S
i
} для 1≤ i ≤ n и h(A)={A} для любого
A∈V
N
;
1
{() }.
i
n
i
PPAhA P
=
′
=∪→α→α∈
∪
Ясно, что грамматика G
’
является контекстно-свободной, возможно, с
правилами вида A →ε. Очевидно, что f(L(G)) = L(G
’
).
Пример 9.2. Пусть L = {0
n
1
n
| n ≥ 1}. Язык L порождается грамматикой
G =({S}, {0, 1}, {S → 0S1, S → 01}, S).
Как и в примере 9.1, пусть f(0) = {a} и f(1) = {ww
R
| w∈{b, c}
*
}.
f(0) порождается грамматикой G
1
= ({S
1
}, {a}, {S → a}, S
1
), а
f(1) — грамматикой
G
2
= ({S
2
}, {b, c}, {S
2
→ bS
2
b, S
2
→ cS
2
c, S
2
→ε}, S
2
).
Язык f(L) порождается грамматикой G
3
= ({S, S
1
, S
2
}, {a, b, c}, {S → S
1
SS
2
,
S → S
1
S
2
, S
1
→ a, S
2
→ bS
2
b, S
2
→ cS
2
c, S
2
→ ε}, S). Первые два правила
грамматики G
3
получились из правил S → 0S1 и S → 01 грамматики G
1
в
результате подстановки символа S
1
вместо 0 и символа S
2
— вместо 1.
() ().
xL
f
Lfx
∈
=
∪

Страницы