Определение Язык L(G) называется языком типа k, если его можно описать грамматикой типа k, где k – максимально возможный номер типа грамматики.

Пример Примеры различных типов формальных языков и грамматик по классификации Хомского. Терминалы будем обозначать строчными символами, нетерминалы – прописными буквами, начальный символ грамматики – S.

а) Язык типа 0 L(G)= определяется грамматикой с правилами вывода:

1) S ® aaCFD; 2) AD ® D;

3) F ® AFB | AB;4) Cb ® bC;

5) AB ® bBA;6) CB ® C;

7) Ab ® bA;8) bCD ® e.

б) Контекстно-зависимый язык L(G)={aⁿbⁿcⁿ | n³1} определяется грамматикой с правилами вывода:

1) S ® aSBC | abc ;2) bC ® bc;

3) CB ® BC;4) cC ® cc;

5) BB ® bb.

в) Контекстно-свободный язык L(G)={(ab)ⁿ(cb)ⁿ | n>0 } определяется грамматикой с правилами вывода:

1) S ® aQb | accb;

2) Q ® cSc.

г) Регулярный язык L(G)={w^ | wÎ{a, b}⁺, где нет двух рядом стоящих а} определяется грамматикой с правилами вывода:

1) S ® A^ | B^;

2) A ® a | Ba;

3) B ® b | Bb | Ab.

4.Задача разбора

4.1. Вывод цепочек

Выводом называется процесс порождения предложения языка на основе правил определяющей язык грамматике. Чтобы дать формальное определение процессу вывода, необходимо ввести еще несколько дополнительных понятий.

ОпределениеЦепочка b Î (V_TÈV_N)^* непосредственно выводима из цепочки в грамматике (обозначается:aÞb), если и , где , и правило вывода содержится во множестве Р.