Составители:
46
Глава 4
КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ
§ 4.1. Упрощение
контекстно-свободных грамматик
В этой главе мы опишем некоторые основные упрощения КС-грамматик и
докажем несколько важных теорем о нормальных формах Хомского и Грейбах.
Мы также покажем, что существуют алгоритмы для определения, является ли
язык, порождаемый КС-грамматикой, пустым, конечным или бесконечным.
Будет определено так называемое свойство самовложенности КС-грам-
матик и показано, что КС-язык нерегулярен тогда и только тогда, когда каждая
КС-грамматика, порождающая его, обладает этим свойством.
Наконец, мы рассмотрим специальные типы КС-грамматик, такие, как
последовательные и линейные грамматики.
Формальное определение КС-грамматики допускает структуры, которые в
некотором смысле являются “расточительными”. Например, словарь может
включать нетерминалы, которые не могут использоваться в выводе хоть какой-
нибудь терминальной цепочки или во множестве правил не запрещено иметь
такое правило, как A → A. Мы докажем несколько теорем, которые показы-
вают, что каждый КС-язык может порождаться КС-грамматикой специального
вида. Более того, будут даны алгоритмы преобразования любой КС-грам-
матики в одну из упомянутых нормальных форм.
Будем предполагать, что КС-грамматики, рассматриваемые в этой главе,
не содержат ε-правил.
В следующей теореме мы докажем результат, который важен сам по себе.
Теорема 4.1. Существует алгоритм для определения, является ли язык,
порождаемый данной КС-грамматикой, пустым.
Доказательство. Пусть G = (V
N
, V
T
, P, S) — контекстно-свободная грам-
матика. Предположим, что существует вывод вида S x некоторой терминаль-
ной цепочки x. Рассмотрим дерево вывода, представляющее этот вывод.
Предположим, что в этом дереве есть путь с узлами n
1
и n
2
, имеющими одну и
ту же метку A∈V
N
. Пусть узел n
1
расположен ближе к корню S, чем узел n
2
(см.
рис. 4.1, a).
Поддерево с корнем n
1
представляет вывод A x
1
цепочки x
1
. Аналогично,
поддерево с корнем n
2
представляет вывод A x
2
цепочки x
2
. Заметим, что x
2
является подцепочкой цепочки x
1
, которая, впрочем, может совпадать с ней.
Кроме того, цепочка x = x
3
x
1
x
4
, где x
3
, x
4
∈Σ
*
, причём одна из них или обе могут
быть пустыми цепочками.
Если в дереве с корнем S мы заменим поддерево с корнем n
1
поддеревом с
корнем n
2
, то получим дерево (см. рис. 4.1, б), представляющее вывод S x
3
x
2
x
4
.
Так мы исключили, по крайней мере, один узел (n
1
) из исходного дерева
вывода.
*
⇒
*
⇒
*
⇒
*
⇒
Страницы
- « первая
- ‹ предыдущая
- …
- 45
- 46
- 47
- 48
- 49
- …
- следующая ›
- последняя »
