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

UptoLike

ВУЗ: 

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

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

Рубрика: 

57
§ 4.4. Разрешимость конечности
контекстно-свободных языков
В теореме 4.2 было показано, что из контекстно-свободной грамматики
можно исключить те нетерминалы, которые не порождают терминальных
цепочек. Фактически можно добиться большéго. Мы можем протестировать,
является ли язык, порождаемый из данного нетерминала, конечным или
бесконечным, и исключить те нетерминалы, кроме начального, из которых
можно породить только конечное число терминальных цепочек. При
доказательстве этого утверждения, мы покажем два результата (теоремы 4.7 и
4.8), интересные и сами по себе.
Теорема 4.7 — “uvwxy”. Пусть L — контекстно-свободный язык.
Существуют постоянные p и q, зависящие только от языка L, такие, что если
существует z∈L при | z| > p, то цепочка z представима в виде z = uvwxy, где
|vwx|≤q, причём v, x одновременно не пусты, так что для любого целого i ≥ 0
цепочка uv
i
wx
i
y∈L.
Доказательство. Пусть
G =(V
N
, V
T
, P, S) — какая-нибудь контекстно-
свободная
грамматика в нормальной форме Хомского для языка L. Если #V
N
= k,
положим p =2
k –1
и q =2
k
. Докажем теорему для этих значений p и q.
Заметим, что дерево вывода любой терминальной цепочки в грамматике G
является бинарным. Поэтому, если в нём нет пути, длиннее j, то выводимая
терминальная цепочка не длиннее 2
j –1
.
Пусть существует z ∈L, причём |z| > p =2
k –1
. Тогда самый длинный путь в
дереве вывода цепочки z длиннее k, ибо в противном случае | z|≤2
k –1
, и это
противоречило бы предположению, что | z| > p.
Рассмотрим самый длинный путь R в дереве вывода z от корня до листа. В
нём должны быть два узла: n
1
и n
2
, удовлетворяющие следующим условиям:
1) они имеют одинаковые метки, скажем, A ∈V
N
;
2) узел n
1
ближе к корню, чем узел n
2
;
3)
часть пути R от узла n
1
до листа
5
имеет длину равную, самое большее, k + 1.
Чтобы убедиться в том, что такие узлы всегда можно найти, пройдем путь R
от листа в сторону корня. Из первых k +2 пройденных узлов только один имеет
терминальную метку. Остальные k +1 узлов не могут быть помечены разными
нетерминалами.
Рассмотрим
поддерево T
1
с корнем n
1
. Его результат, являющийся
подсловом слова z, обозначим через z
1
. В поддереве T
1
не может быть пути,
длиннее k +1, так как R является самым длинным путем во всем дереве T.
Действительно, пусть R = Sn
1
+ n
1
a. Если допустить, что в T
1
существует
другой, более длинный, путь, скажем n
1
b, то путь R
’
= Sn
1
+ n
1
b окажется длин-
нее R, так как n
1
b длиннее n
1
a. Однако это противоречило бы первоначальному
предположению, что R является самым длинным путем во всем дереве T.
Потому |z
1
|≤2
k
= q. Эти рассуждения иллюстрирует рис. 4.2.
5
Очевидно, что самый длинный путь в дереве вывода всегда содержит лист

Страницы