Пример 2. В грамматике G1 из примера 1 S => aaaAbbb , так как существует вывод

В грамматике G1 из примера 1 S => aaaAbbb, так как существует вывод

S→aAb→aaAbb→aaaAbbb,

при этом длина вывода равна 3.

Определение

Языком, порождаемым грамматикой G, называют множество

,то есть L(G) – это все цепочки в алфавите VT, которые выводимы из начального символа S с помощью правил вывода P.

Такие цепочки языка называют сентенциальными формами.

Пример 3

Рассмотрим грамматику G2, где множество правил вывода имеет вид:

S→ aSb, S →ab.

При применении первого правила всегда остается один нетерминальный символ. После второго правила получаем сентенциальную форму. Таким образом, очевиден единственный порядок применения – несколько раз использовать первое правило, а затем один раз применить второе. Тогда