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

UptoLike

ВУЗ: 

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

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

Рубрика: 

128
Контекстно-зависимые языки не замкнуты относительно подстановки.
Однако мы можем несколько смягчить этот факт.
Определение 9.2. Подстановка f называется ε-свободной (ε-free), если
ε∉f(a) для каждого a∈Σ.
Теорема 9.8. Класс контекстно-зависимых языков замкнут относительно
ε-свободной подстановки.
Доказательство. Рассмотрим контекстно-зависимую грамматику G =
(V
N
,
{a
1
, a
2
,…, a
n
}, P, S) и ε-свободную подстановку f. Пусть для каждого i,
1 ≤ i ≤ n, G
i
=(V
N
i
, V
T
i
, P
i
, S
i
) — контекстно-зависимая грамматика, порождаю-
щая множество f(a
i
). Без потери общности предполагаем, что все нетер-
минальные словари попарно не пересекаются. Кроме того, предполагаем, что
все правила, за возможным исключением S →ε, имеют вид α→β или A → a,
где α, β — непустые строки нетерминалов, A — отдельный нетерминал, а a —
отдельный терминальный символ.
Мы построим грамматику где
1.
N
NN N
1
{ }.
i
L
n
i
VV V AAV
=
=∪ ∪ ∈
∪
'
2.
TT
1
.
i
n
i
VV
=
=
∪
'
3. P’ содержит
а) S
L
→ε, если S →ε∈P;
б) A
L
α→B
L
β и Aα→Bβ, если Aα→Bβ∈P (заметим, что индекс L в
обозначении A
L
помечает самое левое вхождение соответствующего нетерми-
нального символа в выводе в грамматике G до тех пор, пока этот символ не
превратится в терминальный символ);
в) A
L
→ S
i
, если A → a
i
∈P,
aA → aS
i
для всех a ∈ V
T
’, если A → a
i
∈P;
г) все правила из множества
{P
i
| i =1, 2,…, n}.
Грамматика G
’ — контекстно-зависимая и L(G’)=f (L(G)).
Теорема 9.9. Класс контекстно-зависимых языков не замкнут относи-
тельно подстановки.
Доказательство. Пусть G
1
=(V
N
, V
T
, P
1
, S) — грамматика типа 0, такая, что
L(G
1
) не является контекстно-зависимым языком. Снова мы предполагаем без
потери общности, что все её правила имеют вид α→β или A → a, где α∈V
N
+
,
β∈V
N
*
, A∈V
N
, a∈V
T
.
Пусть c — новый символ. Рассмотрим грамматику G
2
= (V
N
, V
T
∪ {c}, P
2
, S),
в которой P
2
содержит правила:
1) α→β, если α→β∈P
1
и |α| ≤ |β|
;
2) α→βcc…c, где |α| = |βcc…c|, если α→β∈P
1
и |α| > |β|;
3) cA → Ac для всех A∈V
N
.
Грамматика G
2
является контекстно-зависимой, поскольку мы принудили
правую часть каждого правила иметь, по крайней мере, такую же длину, как
левая. Правила cA → Ac были добавлены для того, чтобы передвигать символы
NT
(,,, ),
L
GVVPS
′′
=
''

Страницы