Автоматные грамматики и конечные автоматы

Классификация формальных грамматик

Н.Хомский предложил разделение грамматик на четыре типа в зависимости от вида их правил.

Тип 0 . Произвольная грамматика (грамматика общего вида). На вид их правил не накладывается никаких ограничений. Правила имеют вид: , где и b - цепочки терминалов и нетерминалов. Цепочка не должна быть пустой.

Примером грамматики типа 0 является грамматика G=({A,S}, {0,1},P,S), где P={S®0A1,0A®00A1,A®e}.

Тип 1 . Контекстно-зависимая грамматика (КЗ-грамматика) – это грамматика, правила вывода которой имеют вид: , где - цепочки терминалов и нетерминалов, А- нетерминальный символ. Цепочки и b называются соответственно правым и левым контекстом. Они задают условия вывода: для любой цепочки замена нетерминала А возможна только в контексте и b. Языки, порождаемые КЗ-грамматиками называются контекстно-зависимыми языками.

Примером КЗ-грамматики является грамматика G=({B,C,S},{a,b,c},P,S),

где P={ S®aSBC, S®abC, CB ®BC, bB®bb, bC®bc,cC®cc}

Тип 2 . Контекстно-свободная грамматика (КС-грамматика) . Правила имеют вид:

,

где А- нетерминал, g - цепочка терминалов и нетерминалов. Характерная особенность – в левой части правил всегда один нетерминальный символ.

Языки, порождаемые КС-грамматиками называются контекстно-свободными языками.

Примером КС-грамматики является грамматика G=({Е,Т,В},{I,+,*,(,)}, P, E),

где P = {Е®Е+Т, Е®Т, Т ®Т*В, Т®В, В®i, B®(E)}

Тип 3 . Автоматные (регулярные) грамматики. Все правила имеют одну из трех форм:

A®aB

A®a

A®e,

Где A, B – нетерминалы, a- терминал, e - пустая цепочка

Языки, порождаемые автоматными-грамматиками называются автоматными (регулярынми) языками.

Примером автоматной грамматики является грамматика G=({А,S},{0,1}, P, S),

где P = {S®0A, S®1A, A ®0A, A®0, A®1}