Пример 5. 1. Грамматика G2 из примера 3 является контекстно-свободной грамматикой

1. Грамматика G2 из примера 3 является контекстно-свободной грамматикой.

2. Грамматика G, где множество правил имеет вид

является контекстно-свободной грамматикой. Грамматика порождает язык

L(G)={(aс)n, (сb)n | n>0}

• Тип G3 (автоматные или регулярные грамматики). Грамматику G называют грамматикой типа 3, если каждое ее правило имеет вид:

Пример 6

Грамматика G, где множество правил имеет вид

является регулярной грамматикой. Грамматика G порождает язык

. L(G)={(an, b2 | n>1}

Классы грамматик типа G0, G1, G2 и G3 образуют иерархию Хомского.