Основы конструирования компиляторов



             

Типы грамматик и их свойства - часть 2


Шаг 4. Если S

Ni, значитS
e.

Легко видеть, что G' - неукорачивающая грамматика. Можно показать по индукции, что L(G') = L(G). __

Пусть Ki - класс всех языков типа i. Доказано, что справедливо следующее (строгое) включение: K3

K2
K1
K0.

Заметим, что если язык порождается некоторой грамматикой, это не означает, что он не может быть порожден грамматикой с более сильными ограничениями на правила. Приводимый ниже пример иллюстрирует этот факт.

Пример 2.8. Рассмотрим грамматику G = ({S, A, B}, {0, 1}, {S

AB, A
0A, A
0, B
1B, B
1}, S). Эта грамматика

является контекстно-свободной. Легко показать, что L(G) = {0n1m|n, m > 0}. Однако, в примере 2.7 приведена праволинейная грамматика, порождающая тот же язык.

Покажем что существует алгоритм, позволяющий для произвольного КЗ-языка L в алфавите T, и произвольной цепочки w

T*

определить, принадлежит ли w языку L.

Теорема 2.2. Каждый контекстно-зависимый язык является рекурсивным языком.

Доказательство. Пусть L - контекстно-зависимый язык. Тогда существует некоторая неукорачивающая грамматика G = (N, T, P, S), порождающая L.

Пусть w

T* и |w| = n. Если n = 0, т.е. w = e, то принадлежность w
L проверяется тривиальным

образом. Так что будем предполагать, что n > 0.

Определим множество Tm

как множество строк u

(N
T)+

длины не более n таких, что вывод S

*u имеет не более m шагов. Ясно, что T0 = {S}.

Легко показать, что Tm можно получить из Tm-1

просматривая, какие строки с длиной, меньшей или равной n можно вывести из строк из Tm-1

применением одного правила, т.е.

Если S

*u и |u|
n, то u
Tm для некоторого

m. Если из S не выводится u или |u| > n, то u не принадлежит Tm ни для какого m.

Очевидно, что Tm

Tm-1 для всех m
1. Поскольку Tm зависит только от Tm-1, если Tm = Tm-1, то Tm = Tm+1 = Tm+2 = ... . Процедура будет вычислять T1, T2, T3, . . . пока для некоторого m не окажется Tm = Tm-1. Если w не принадлежит Tm, то не принадлежит и L(G), поскольку для j > m выполнено Tj = Tm. Если w
Tm, то S
*w.




Содержание  Назад  Вперед