Составители:
59
Пусть язык L = L(G) бесконечен. Тогда в нём имеются сколь угодно
длинные цепочки и, в частности, цепочка длиной больше p + q. Эта цепочка
может быть представлена как uvwxy, где |vwx|≤q , |v| + |x|>0, и цепочка
uv
i
wx
i
y∈L для любого i ≥ 0. При i =0 заключаем, что цепочка uwy ∈L и
|uwy| < |uvwxy|.
Убедимся в том, что |uwy| > p. Так как p + q < |uvwxy| и q ≥|vwx|, то
p < |uy|≤|uwy|. Если |uwy| > p + q, то эту процедуру можно повторять снова
до тех пор, пока мы не найдем цепочку в языке L, длина которой l не будет
удовлетворять неравенству p < l ≤ p + q.
Таким образом, язык L бесконечен тогда и только тогда, когда он содержит
цепочку длиной l, p< l ≤ p + q. Поскольку мы можем проверить, имеется ли
данная цепочка в данном контекстно-свободном языке L (см. теорему 2.2 о
рекурсивности контекстно-зависимых грамматик), то мы просто должны
проверять все цепочки в интервале длин между p и p+ q на принадлежность
языку L(G). Если такая цепочка имеется, то ясно, что язык L бесконечен; если в
языке L нет цепочек длиной больше p, то язык L конечен.
Что и требовалось доказать.
В теореме 4.2 доказывалось, что из контекстно-свободной грамматики
можно исключить все нетерминалы, из которых не выводится ни одной
терминальной цепочки. Теперь мы докажем возможность исключения
нетерминалов, из которых выводится только конечное число терминальных
цепочек.
Теорема 4.9. Для всякой контекстно-свободной грамматики G
1
можно
найти эквивалентную ей контекстно-свободную грамматику G
2
, такую, что
если A — нетерминал грамматики G
2
, не являющийся начальным нетерми-
налом, то из A выводимо бесконечно много терминальных цепочек.
Доказательство. Если язык L(G
1
) = {x
1
, x
2
, ..., x
n
} конечен, то утверждение
очевидно. Действительно, положим G
2
= ({S}, V
T
, P
2
, S), где P
2
= {S → x
i
| i = 1,
2, ..., n
}. В этой грамматике совсем нет нетерминалов, отличных от S.
Пусть теперь грамматика G
1
=(V
N
, V
T
, P
1
, S) и язык L(G
1
) бесконечен.
Рассмотрим грамматики G
A
= (V
N
, V
T
, P
1
, A) для всех A∈V
N
. Так как существует
алгоритм, позволяющий узнать, бесконечен ли порождаемый грамматикой G
A
язык, то весь словарь V
N
мы можем разбить на две части: V
N
={A
1
, A
2
, ..., A
k
} ∪
{B
1
, B
2
, ..., B
m
}, где A
i
(i = 1, 2, ... , k) — нетерминалы, порождающие бесконечно
много терминальных
цепочек, причём начальный нетерминал S среди них,
поскольку язык L бесконечен; B
j
(j = 1, 2,... , m) — нетерминалы, порождающие
конечные множества терминальных цепочек.
Построим
грамматику G
2
= ({A
1
, A
2
, ..., A
k
}, V
T
, P
2
, S), где
P
2
= {A
i
→ u
1
u
2
... u
r
| ∃ A
i
→ C
1
C
2
... C
r
∈P
1
,
(1) u
i
= C
i
, если C
i
∈ V
T
∪ {A
1
, A
2
, ..., A
k
},
(2) C
i
u
i
, u
i
∈V
T
*
, если C
i
∈{B
1
, B
2
, ..., B
m
}}.
1
*
G
⇒
Страницы
- « первая
- ‹ предыдущая
- …
- 58
- 59
- 60
- 61
- 62
- …
- следующая ›
- последняя »
