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

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

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

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

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

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

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

 

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

 

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

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

L(G5) = L(G4)

 

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

 

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

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

 

Пример.

 

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

S ®aAc A ®aABc A® b bB®bb cB ®Bc     L(G6)= {anbncn, n³1}

 

 

Эквивалентная ей контекстная грамматика G7. В ней правило переноса символа С заменяется на 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½.

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

 

 
 

 

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