Иерархия языков по Хомскому

Определение 9.4.1. Формальный язык называется языком типа 0, если он порождается некоторой грамматикой типа 0.

Определение 9.4.2. Контекстной грамматикой (контекстно-зависимой грамматикой, грамматикой типа 1) называется порождающая грамматика, каждое правило которой имеет вид hBq ® h a q, где BÎN, h,qÎ (NÈA)^*, a Î (NÈA)⁺.

Определение 9.4.3. Формальный язык называется контекстным языком, если он порождается контекстной грамматикой (грамматикой типа 1).

Определение 9.4.4. Контекстно-свободной грамматикой (бесконтекстной грамматикой, грамматикой типа 2) называется порождающая грамматика, каждое правило которой имеет вид B ®a, где BÎN, a Î (NÈA)^*.

Пример 9.4.1. Пусть N ={ S, U, T }, A ={ a, b, c }, P ={ S®UT, U®aU, U®e, T®bTc, T®e }. Тогда G=< N, A, P, S > – контекстно-свободная грамматика, порождающая язык

L (G)={aⁿb^mc^m: n³0, m³0 }

Определение 9.4.5. Формальный язык называется контекстно-свободным языком, если он порождается контекстно-свободной грамматикой (грамматикой типа 2).

Определение 9.4.6. Праволинейной грамматикой (рациональной грамматикой, грамматикой типа 3) называется порождающая грамматика, каждое правило которой имеет вид B ® w или B ® wT, где B, TÎN, wÎA ^*.

Определение 9.4.7. Формальный язык называется праволинейным языком, если он порождается праволинейной грамматикой (грамматикой типа 3).

Классы формальных языков типа 0, 1, 2, 3 образуют иерархию Хомского. При этом следует иметь в виду, что:

1) каждая праволинейная грамматика является контекстно-свободной грамматикой;

2) каждая контекстно-свободная грамматика без правил вида a® e является контекстной грамматикой;

3) каждая контекстная грамматика является порождающей грамматикой типа 0.

Пример 9.4.2. Пусть N= { S, H }, A= { a, b }, P= { S ® aS, S ® a, S ® H, H ® bH, H ® b }. Тогда G=< N, A, P, S > – праволинейная грамматика, порождающая язык L (G)={ aⁿb^m: n³1 или m³1 }.