Классификация грамматик. 
Построение эквивалентной праворекурсивной КС-грамматики

Правила порождающих грамматик позволяют осуществлять преобразования строк. Ограничения же на виды правил позволяют выделить классы грамматик. Рассмотрим классификацию, которую предложил Н. Хомский.

Грамматики типа 0 — это грамматики, на правила вывода которых нет ограничений.

Грамматики типа 1, или контекcтные грамматики — это грамматики, все правила которых имеют следующий вид: хАу > х? у, где A? VN, x, y,? ? (VN? VT)+. Грамматики типа 2 — это бесконтекстные, или контекстно-свободные грамматики (КСграмматики). Правила вывода для этих грамматик имеют следующий вид: А > ?, где, А? VN,? ? (VN? VT)*.

Грамматики типа 3 — это автоматные грамматики, которые делятся на два типа:

а) леволинейные (леворекурсивные), правила вывода для которых имеют следующий вид: А > Аа | a, где, А? VN; б) праволинейные (праворекурсивные), правила вывода для которых имеют следующий вид: А > Aа | a.

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

Методика решения задач

Пример 1. Дана порождающая грамматика G = (VT, VN, Р, S), в которой VT = {a, d, е}, VN = {В, С, S}, Р = {S > аВ, В > Cd | dC, С > е}. Выписать терминальные цепочки, порожденные данной грамматикой, и определить длину их вывода.

Решение. Получим следующие терминальные цепочки:

• S > аВ > aCd > aed,
• S > аВ > adC > ade,

длина вывода которых равна 3.

Пример 2. Дана грамматика G = (VT, VN, Р, C), в которой VT = {a, b, c, d, е}, VN = {A, В, С, D, E}, Р = {A > ed, В > Ab, С > Bc, С > dD, D > Ae, E > bc}. Определить, принадлежит ли языку L (G) цепочка eadabcb.

Решение. Выведем возможные терминальные цепочки из аксиомы с помощью заданных правил вывода:

С > Bc > Abc > edbc,.

С > dD > dAe > dede.

Так как первые же терминальные символы полученных цепочек не совпадают с заданной, можно сделать вывод о том, что цепочка eadabcb не принадлежит языку L (G).

Пример 3. Построить КС-грамматику (грамматику типа 2), порождающую цепочки из 0 и 1 с одинаковым числом тех и других символов.

Решение. Определим множества, задающие грамматику:

VT = {0, 1}; VN = {S}; Р = {S > 0S1, S > 1S0, S > е, S > S01, S > S10}.

Пример 4. Описать язык, порождаемый следующими правилами:

S > bSS | а.

Решение. Построим несколько терминальных цепочек, применяя заданные правила вывода:

• S > a;
• S > bSS > baa;
• S > bSS > bbSSS > bbaaa;
• S > bSS > bbSSbSS > bbaabaa;
• S > bSS > bbSSbSS > bbbSSbSSbbSSbSS > …

Из полученных цепочек видно, что:

• а) цепочки всегда начинаются с терминала b, кроме аксиомы, и заканчиваются терминалом а;
• б) количество терминалов, а в любой цепочке всегда на 1 больше, чем b.

Исходя из этих выводов, определим язык, порождаемый заданными правилами, следующим образом:

L (G) = {б | б? {a, b}*}, |a| = |b| + 1.

причем цепочки начинаются с терминала b и заканчиваются терминалом а.