18c0693f

Типы грамматик и их свойства


Рассмотрим классификацию грамматик (предложенную Н.Хомским), основанную на виде их правил.

Определение. Пусть дана грамматика G = (N, T, P, S). Тогда

Легко видеть, что грамматика в примере 2.5 - неукорачивающая, в примере 2.6 - контекстно-свободная, в примере 2.7 - праволинейная.

Язык, порождаемый

грамматикой типа i, называют языком типа i. Язык типа 0 называют также языком без ограничений, язык типа 1 - контекстно-зависимым (КЗ), язык типа 2 - контекстно-свободным (КС), язык типа 3 - праволинейным.

Теорема 2.1. Каждый контекстно-свободный язык может быть порожден неукорачивающей контекстно-свободной грамматикой.

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

Построим новую грамматику G' = (N', T, P', S') следующим образом:

1. Если в P есть правило вида A

0B1
1...Bk
k, где k
0, Bi
+e для 1
i
k, и ни из одной

цепочки

j (0
j
k) не выводится e, то включить в P' все правила (кроме A
e) вида

где Xi - это либо Bi, либо e.

2. Если S

+e, то включить в P' правила S'
S, S'
e и положить N' = N
{S'}. В противном случае положить N' = N и S' = S.

Порождает ли грамматика пустую цепочку можноо установить следующим простым алгоритмом:

Шаг 1. Строим множество N_0 = N | N

e

Шаг 2. Строим множество N_i = N | N

Ni - 1*

Шаг 3. Если N_i = N_i-1, перейти к шагу 4, иначе шаг 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.



Покажем, что существует такое m, что Tm = Tm-1. Поскольку для каждого i
1 справедливо Ti
Ti-1, то если Ti
Ti-1, то число элементов в Ti по крайней мере на 1 больше, чем в Ti-1. Пусть |N
T| = k. Тогда число строк в (N
T)+ длины меньшей или равной

n равно k + k2 + ... + kn
nkn. Только эти строки могут быть в любом Ti. Значит, Tm = Tm-1 для некоторого m
nkn. Таким образом, процедура, вычисляющая Ti для всех i
1 до тех пор, пока не будут найдены два равных множества, гарантированно заканчивается, значит, это алгоритм. __




Все публикации раздела