Классификация грамматик по Хомскому

В 1956 году Н.Хомским было предложено классифицировать грамматики по виду их правил, по ограничениям, накладываемым на правила.

Грамматика Gпо Хомскому-это традиционная четверка множеств

G = (N, S, R, S),

где N - множество нетерминалов, S - множество терминалов, R - множество продукций, S - аксиома грамматики.

Грамматика G называется грамматикой типа 3, регулярной, праволинейной или автоматнойграмматикой(А-грамматикой), если каждое правило из R имеет вид:

A ® xA (праволинейное правило)

или

A ® x (заключительное правило)

где AÎ N, xÎ S.

То есть каждое правило такой грамматики содержит единственный нетерминал в левой части, всегда один терминал в правой части, за которым может следовать один нетерминал. Для таких грамматик мы в дальнейшем будем пользоваться термином автоматная (А-) грамматика.

Грамматика G называется грамматикой типа 2, бесконтекстной или контекстно - свободной(КС- ) грамматикой если ее правила имеют вид:

A ® a,

где AÎ N, aÎ (NÈS) ^*.

То есть в каждом правиле такой грамматики имеет место единственный нетерминал слева и произвольная цепочка из терминалов и нетерминалов справа, возможно и пустая. Замена A на a в сентециальной форме не зависит от того, в каком окружении, в каком контексте находится A.

Грамматика G называется грамматикой типа 1, контекстной, нормальных составляющих(НС-) или контекстно - зависимой(КЗ- ) грамматикой если ее правила имеют вид:

jAy ® jay,

где AÎ N, j, y Î (NÈS)^*È и aÎ (NÈS)⁺, то есть в каждом правиле нетерминал A в контексте j и y заменяется на непустую цепочку a в том же контексте.

Грамматика G называется грамматикойтипа 0, грамматикой с фразовой структуройили рекурсивно перечислимой грамматикой, если ее правила имеют вид:

a®b,

где на левую и правую части правил не наложено никаких ограничений. “

Нетрудно заметить, что грамматики типа i одновременно являются грамматиками типа i -1. Исключение составляют укорачивающие КС (УКС) - грамматики, то есть грамматики, содержащие аннулирующие правила типа

A ® e

которые не являются КЗ-грамматиками.

Язык, определяемый грамматикой типа i называется языком типа i.

Из примеров 1.2 и 1.3 следует, что языки чисел и идентификаторов являются КС-языками (тип 2).

Тот факт, что язык определяется грамматикой типа i, еще не означает, что его нельзя породить менее мощной грамматикой типа i+1. Например, КС- грамматика с правилами

S®AS ç e

A ® 0 ç 1

порождает язык {0,1}^*, который конечно же можно определить А-грамматикой

S ® 0S ç 1S ç e

Рассмотрим ряд примеров грамматик. В большинстве случаев мы опускаем описания множеств N, S, Sв силу их очевидности и ограничиваемся множеством правил грамматики R.

Пример 1.4.Автоматная грамматика идентификатора.

S ® aA ç bA ç cA ç...ç yA ç zA

A ® aA ç bA ç cA ç...ç yA ç zA ç 0A ç 1A ç... ç 8A ç 9A

A ® a ç b ç c ç ... ç yç z ç 0 ç 1 ç... ç 8 ç 9.

Данная грамматика имеет на самом деле 72 правила, но для краткости часть из них заменена многоточием. ™

Пример 1.5.Грамматика типа 0 для цепочек вида x ⁿ y ⁿ z ⁿ, где n > 0.

(1) S ® xyASz

(2) S ® Q

(3) yAQ ® Qy

(4) yAx®xyA

(5) xQ®x

Покажем, что данная грамматика порождает цепочки x ⁿ y ⁿ z ⁿ и никаких других.

1). Новые символы порождаются только первым правилом. При этом получается одинаковое количество символов x, y и z, символы z в нужном месте и порядке. То есть применяя n раз правило (1) получим вывод:

S Þ xyASz Þ xyAxyASzz Þ^* (xyA) ⁿ Sz ⁿ.

2). После применения правила (2) дальнейшее порождение новых символов невозможно. Получаем (xyA) ⁿ Sz ⁿ Þ (xyA) ⁿ Qz ⁿ.

3). Правила (3) и (4) применяются поочередно. При этом А устраняется правилом (3), когда правее него в сентенциальной форме нет х. Получаем

(xyA) ⁿ Qz ⁿ = (xyA) ^n-1 xyAQz ⁿ Þ (xyA) ^n-2 xyAxQyz ⁿ Þ ( xyA) ^n-2 xxyAQyz ⁿ Þ

(xyA) ^n-3 xyAxxQyyz ⁿ Þ (xyA) ^n-3 xxyAxQyyz ⁿ Þ (xyA) ^n-3 xxxyAQyyz ⁿ Þ⁺ x ⁿ Qy ⁿ z ⁿ

4). x ^n-1 xQy ⁿ z ⁿ Þ x ⁿ y ⁿ z ⁿ

Применить правило (5) можно только на последнем шаге, в противном случае в цепочке останутся нетерминалы A. ™