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

UptoLike

ВУЗ: 

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

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

Рубрика: 

58
Обозначим через T
2
поддерево с корнем n
2
, а его результат — через z
2
. Ясно,
что цепочка z
1
представима в форме z
1
= z
3
z
2
z
4
, где z
3
и z
4
одновременно не
пусты. Действительно, если первое правило, используемое в выводе z
1
, имеет
вид A → BC, то поддерево T
2
должно быть полностью в пределах либо
поддерева с корнем B, либо поддерева с корнем C.
Иллюстрирует три случая: (a) когда B есть корень поддерева T
2
(z
3
= ε),
(
б) C есть корень поддерева T
2
(z
4
= ε), (в) корень поддерева T
2
расположен внутри поддерева
B (z
3
≠ε, z
4
≠ε).
Рис. 4.3.
Теперь мы знаем, что A z
3
Az
4
и, само собой разумеется, что A
z
2
. Поэто-
му A
z
3
i
z
2
z
4
i
для любого i ≥ 0 и цепочка z представима в виде z = uz
3
z
2
z
4
y для
некоторых u,y∈V
T
*
.
Чтобы закончить доказательство, положим v = z
3
, w = z
2
и x = z
4
.
Теорема 4.8. Существует алгоритм для определения, порождает ли
данная контекстно-свободная грамматика G конечный или бесконечный язык.
Доказательство. Пусть p и q — константы, определяемые теоремой 4.7.
Если z∈L(G) и |z | > p, то z = uvwxy при некоторых u,v, w, x, y∈V
T
*
, |v| + |x|>0,
и для любого i ≥ 0 цепочка uv
i
wx
i
y ∈L(G). Следовательно, если в языке L(G)
существует цепочка длиной больше p, то язык L(G) бесконечен.
*
G
⇒
*
G
⇒
*
G
⇒
Рис. 4.2.

Страницы