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



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


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

Пример 2.6. Рассмотрим грамматику

G \;= \; (\{S\},\{0,1\},\{S \rightarrow 0S1,\;S\rightarrow01\},S)
. Легко видеть, что цепочка
000111 \in L(G)
, так как существует вывод

S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 000111

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

L(G)\; = \; \{0^n1^n \mid n>0\}
.

Пример 2.7. Рассмотрим грамматику

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




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