Составители:
22
§ 2.5. Рекурсивность
контекстно-зависимых грамматик
Напомним, что грамматика G =(V
N
, V
T
, P, S) — рекурсивна, если существует
алгоритм, который определяет (за конечное время), порождается ли любая
данная цепочка
*
T
x
V∈ данной грамматикой G.
Пусть
G = (V
N
, V
T
, P, S) — контекстно-зависимая грамматика. Проверить,
порождается пустое предложение данной грамматикой или нет, просто.
Достаточно посмотреть, имеется ли в ней правило
S →ε, поскольку ε∈L(G)
тогда и только тогда, когда
S →ε∈P. Если ε∈L(G), то мы можем образовать
новую грамматику: G
1
=(V
N
, V
T
, P
1
, S), отличающуюся от исходной лишь тем, что
в ней не будет правила S →ε, т.е. P
1
= P \{S →ε}. Согласно теореме 2.1
грамматика
G
1
тоже контекстно-зависима, и L(G
1
)=L(G)\{ε}. Следовательно,
в любом выводе длина последовательных сентенциальных форм разве лишь
возрастает (т.е. не убывает).
Пусть
объединённый словарь V грамматики G
1
имеет k символов.
Предположим, что
S
x (x ≠ε). Пусть этот вывод имеет вид:
S
α
1
α
2
...
α
m
= x, причём |α
1
| ≤ |α
2
| ≤ ... ≤ |α
m
|.
Предположим, что сентенциальные формы
α
i
, α
i +1
, ..., α
i + j
все одной и той
же длины, скажем,
p. Предположим также, что j ≥ kp. Тогда среди этих
сентенциальных форм, по крайней мере, какие-то две одинаковы,
так как число
всевозможных различных непустых цепочек длиной p, составленных из
символов алфавита
V, в котором k символов, равно kp. В рассматриваемой же
последовательности мы имеем j + 1 цепочек, где j ≥ kp.
Пусть,
например, α
q
= α
r
, где q < r. Тогда
S α
1
α
2
... α
q
α
r +1
... α
m
= x
является более коротким выводом цепочки
x в грамматике G
1
, чем перво-
начальный.
Интуитивно ясно, что если существует какой-нибудь вывод терминальной
цепочки, то существует и “не слишком длинный” её вывод.
В следующей теореме описывается алгоритм распознавания контекстно-
зависимого языка, в котором существенно используется это соображение.
Теорема 2.2. Если грамматика G=(V
N
, V
T
, P, S) — контекстно-зависима,
то она — рекурсивна.
Доказательство. В предыдущих параграфах было показано, что суще-
ствует простой способ узнать, действительно ли
ε∈L(G), и если это так, то,
исключив из грамматики правило
S →ε, получим грамматику, которая
порождает тот же самый язык, но без пустого предложения. Любое же
непустое предложение языка выводимо без использования этого правила.
Поэтому, предполагая, что
P не содержит правила S →ε, рассмотрим произ-
вольную цепочку
+
T
.
x
V∈ Наша задача найти алгоритм, разрешающий вопрос:
“
x ∈L(G)?”
Пусть
|x | = n (n > 0). Определим множество T
m
следующим образом:
T
m
= {α | S α, i ≤ m,
+
,Vα∈ | α | ≤ n}.
1
G
⇒
1
*
G
⇒
i
G
⇒
1
G
⇒
1
G
⇒
1
G
⇒
1
G
⇒
1
G
⇒
1
G
⇒
1
G
⇒
1
G
⇒
1
G
⇒
1
G
⇒
Страницы
- « первая
- ‹ предыдущая
- …
- 21
- 22
- 23
- 24
- 25
- …
- следующая ›
- последняя »
