Лекция №5

1.3.5. Примеры классификации языков и грамматик

Сводная таблица грамматик по Хомскому показана в табл. 1. Классификация языка идет от простого к сложному. Если мы имеем дело с регулярным языком, то он также является и контекстно-свободным, и контекстно-зависимым, и языком с фразовой структурой. В то же время известно, что существуют КС-языки, которые не являются регулярными, и КЗ-языки, которые не являются ни регулярными, ни контекстно-свободными. Используя табл. 1, рассмотрим несколько примеров классификации грамматик.

Пример 1.3.

Задана грамматика для языка L1-языка целых десятичных чисел со знаком:

G1<T1, N1, P1, S1>, где T1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, –},

N1 = {S, T, F}; S1 = {S}

P1: S  T + T – T

T  F TF

F  0 1 2 3 4 5 6 7 8 9

Необходимо определить тип грамматики. Цифрами в правых частях правил пронумерованы правила.

Начнем с типа 3. Возможны 2 класса грамматик:

леволинейная праволинейная

A  B или A   A  B или A  

где A, B  N;   T^* где A, B  N;   T^*

В правилах P1 слева находится один нетерминальный символ и по этому признаку G1 можно отнести к типу 3.

Если посмотреть на правую часть первой строки правил 2 и 3 P1, то можно сказать, что G1 – это праволинейная грамматика.

Посмотрим на вторую строчку правил P1. В правой части правила 4 только нетерминальный символ F. Относится ли это правило к типу 3? Да, относится, так  может быть равна , т. к.   T^*. Тогда правила грамматики типа 3 трансформируются в A  B.

Однако пятое правило T  TF не соответствует типу 3, т. к. в правой части цепочка из двух нетерминальных символов, которая допустима для типа 2. То есть по структуре своих правил G1 относится к контекстно-свободным грамматикам (тип 2, НКС).

Для того же самого языка L1 может построить другую грамматику G1<T1, N1, P1, S1>:

T1 = T1; N1 = {S, T}; S1 = {S,};

P1: S  T +T – T

T  0 1 2 3 4 5 6 7 8 9 0T 1T 2T 3T 4T 5T 6T 7T 8T 9T

По структуре своих правил грамматика G1 является праволинейной и может быть отнесена к регулярным грамматикам (тип 3).

Покажем, что она эквивалентна G1. Сделаем это на примере получения числа (– 157). Это число по грамматике G1 мы получили ранее в п. 1.3.1.

По грамматике G1 это же число получаем следующим образом:

S  – T  – 1T  – 15T  – 157.

Для этого же языка L1 можно построить эквивалентную леволинейную грамматику (тип 3) G1:

G1<T1, N1, P1, S1>

T1 = T1; N1 = N1; S1 = {S}

P1: S  T0 T1 T2 T3 T4 T5 T6 T7 T8 T9 S0 S1 S2 S3

S4 S5 S6 S7 S8 S9 

T  + – 

Для числа (– 157) будет следующий набор правила

S  S7  S57  S157  – 157.

Вопрос к слушателям. Какого типа язык L1?

Пример 1.4.

Задана грамматика для языка L2: G2<T2, N2, P2, S>

T2 = {0, 1}; N2 = {A, S};

P2: S  0A1

0A  00A1

A  .

Эта грамматика относится к типу 0.

Вопрос слушателям. Почему можно сказать, что грамматика G2 относится к типу 0?

Она определяет язык, множество предложений которого

L(G2) = {0ⁿ1ⁿn > 0}.

При n = 1 предложение будет 01;

при n = 2 предложение будет 0011;

при n = 3 предложение будет 000111.

Эти предложения получены из совокупности правил P2 следующим образом:

S  0A1  01  01;

S  0A1  00A11  0011  0011;

S  0A1  00A11  000A111  000111  000111.

Для n = 1 сделано три шага в выводе цепочки 01, для n = 2 – четыре шага, для n = 3 – пять шагов.

Вопрос слушателям. Сколько шагов необходимо сделать для вывода цепочки при n = 5?

Для этого же языка можно построить также контекстно-зависимую (КЗ-грамматику): G2<T2, N2, P2, S>

T2 = T2 = {0, 1}; N2 = N2 = {A, S};

P2: S  0A1 01

0A  00A1 001.

Вопрос слушателям. Как показать, что это K3-грамматика, и что она эквивалентна G2?

Однако для того же самого языка L2 можно использовать и КС-грамматику G2: G2<T2, N2, P2, S>,

T2 = T2 = {0, 1}; N2 = {S};

P2: S  0 S 1 01.

При n = 1 S  01; n = 2 S  0S1  0011; n = 3 S  0S1  00S11  000111;

Следовательно, язык L2 = {0ⁿ1ⁿn > 0} является языком типа 2 (контекстно-свободный).

Пример 1.5.

Задана грамматика G3<T3, N3, P3, S>

T3 = {a, b, c}; N3 = {B, C, D, S}

P3:

S  BD

B  aBbCab

Cb  bC

CD  Dc

bDc  bcc

abD  abc.

Эта грамматика порождает язык L3, множество предложений которого можно записать так: L(G3) = {aⁿbⁿcⁿ n > 0},

Вопрос слушателям. Какой тип языка L3?