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

             

Формальное определение грамматики - часть 2


L(G1) = L(G2).

Пример2.5. Грамматика G = ({S, B, C}, {a, b, c}, P, S), где

P = {S

aSBC, S
aBC, CB
BC, aB
ab, bB
bb, bC
bc, cC
cc}, порождает язык L(G) = {anbncn|n > 0}.

Действительно, применяем n- 1 раз правило 1 и получаем an-1S(BC)n-1, затем один раз правило 2 и получаем an(BC)n, затем n(n- 1)/2 раз правило 3 и

получаем anBnCn.

Затем используем правило 4 и получаем anbBn-1Cn. Затем применяем n- 1 раз правило 5 и получаем anbnCn. Затем применяем правило 6 и n - 1 раз правило 7 и получаем anbncn. Можно показать, что язык L(G) состоит из цепочек только такого вида.

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

0S1, S
01}, S). Легко видеть, что цепочка 000111
L(G), так как существует вывод

Нетрудно показать, что грамматика порождает язык L(G) = {0n1n|n > 0}.

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

0S,

S

0A, A
1A, A
1}, S). Нетрудно показать, что грамматика порождает язык L(G) = {0n1m|n, m > 0}.




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