А-языки. Конечные автоматы

Классификация грамматик

Выделяются определенные классы грамматик, основными среди которых являются контекстно-свободные (КС), контекстно-зависимые (КЗ), автоматные…

Основными типами грамматик являются:

Грамматики класса «0» - не накладывается ограничений на вид правила.

Контекстно-зависимые (КЗ) – грамматики, все правила которых имеют вид j ® y, где j, y Î(V_TÈV_N)* êj ê£ ê y ê

Например, грамматика G₄ с правилами

S ® abA êab bA ® Ab aA ® aabA aA ® aab

Контекстно-свободные (КС- грамматики), все правила которых имеют вид А® y, где А ÎV_N,y Î(V_TÈV_N)*.

Например, грамматика G₅ с правилами S ® a Аb êab.

L(G₅) = L(G₄)

Автоматные (А-грамматики), все правила которых имеют вид А®а, А®a B, А®l, aÎV_T, A,B ÎV_N.

Иногда выделяется еще один класс грамматик: контекстные грамматики, или грамматики класса 1, все правила которых имеют вид aAb®awb, где a, bÎ (V_TÈV_N)*, AÎ V_N, wÎ (V_TÈV_N)*.

Здесь пара цепочек a и b составляет неизменяемый контекст правила. Между контекстными грамматиками и КЗ-грамматиками существует взаимно-однозначное соответствие, не всегда очевидное. По выразительной мощности эти классы грамматик совпадают, однако, поскольку для одного и того же языка контекстная грамматика содержит большее число правил, мы будем изучать именно КЗ-грамматики.

Пример.

Грамматика G₆, КЗ-грамматика

S ®aAc A ®aABc A® b bB®bb cB ®Bc

L(G6)= {anbncn, n³1}

Эквивалентная ей контекстная грамматика G₇. В ней правило переноса символа С заменяется на 3 правила.

S ®ABC B ®ABDC B® b bD®bb CD ®ED ED ®EC EC ®DC C®c

L(G7)= {anbncn, n³1}

В соответствии с классом грамматики, порождающей язык, классифицируются языки. Т.Е. язык, для которого может быть порожден КС- грамматикой, называется КС-языком (т.е. язык, для которого существует порождающая его КС-грамматика, и не существует А-грамматики, порождающей этот язык).

А-язык - язык, для которого может быть построена порождающая его А-грамматика.

КЗ-язык – язык, который может быть построен только КЗ-грамматикой.

Непосредственная классификация грамматик выглядит следующим образом.

Класс А-грамматик включается в класс КС-грамматик. Все грамматики принадлежат классу 0.

Однако класс КС-грамматик не включается в класс КЗ-грамматик, так как правила вида А®l могут принадлежать КС-грамматикам, но не КЗ-грамматикам, т.к. ½ А½>½l½.

Поэтому общий вид классификации следующий:

Для рассмотрения иерархии языков надо больше знать о преобразованиях грамматик.