Задача 1. Покажите, что для грамматики G1 из примера 1 L(G1)=L(G2)

Покажите, что для грамматики G1 из примера 1 L(G1)=L(G2)

Определение

Грамматики G1 и G2, порождающие один и тот же язык L(G1)=L(G2), называют эквивалентными.

Приведенные примеры грамматик очень просты: было почти очевидно, какие цепочки в них можно вывести. В общем случае определить, что же порождается грамматикой, бывает очень трудно. Дадим более сложный пример.

Задача 2

Покажите, что грамматика G, определяемая следующими правилами вывода:

S →aSBC, S →aBC, CB→ BC, aB →ab, bB →bb, bC→bc, cC→cc,

порождает язык

L(G)={an, bn, cn | n>0}

КЛАССИФИКАЦИЯ ГРАММАТИК

Накладывая различные ограничения направила вывода, можно выделить классы грамматик. Рассмотрим классификацию, предложенную Н. Хомским.

• Тип G0 (свободные или неограниченные грамматики). Грамматику G называют грамматикой типа 0, если на ее правила вывода не накладывается никаких ограничений.

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

α→β, |β|≥|α|.

Часто, вместо термина «контекстно-зависимая грамматика», употребляют сокращение csg (context-sensitive grammar).