Теория и реализация языков программирования


         

и получаем anbnCn. Затем применяем


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

Пример 2.6. Рассмотрим грамматику
. Легко видеть, что цепочка
, так как существует вывод



Нетрудно показать, что грамматика порождает язык
.

Пример 2.7. Рассмотрим грамматику
. Нетрудно показать, что грамматика порождает язык



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