Формальное определение грамматики - часть 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\}$

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