8.2.2. Типы грамматик

В этом пункте рассмотрим грамматики, являющиеся частным случаем (8.2.1). Все эти грамматики идоеют форму и различаются лишь по типу правил подстановки, допустимых в каждой из них.

Неограниченная грамматика характеризуется правилами подстановки вида , где а — цепочка алфавита — цепочка алфавита V.

Грамматика непосредственно составляющих характеризуется правилами подстановки вида где элементы алфавита принадлежит , а А принадлежит . Эта грамматика допускает замещение нетерминального символа А цепочкой только в том случае, если А появляется в контексте составленном из цепочек и

Бесконтекстная грамматика характеризуется правилами подстановки вида , где А принадлежит множеству и принадлежит множеству . Само название «бесконтекстная» указывает на то, что переменная А может замещаться цепочкой Р независимо от контекста, в котором появляется А.

Наконец, регулярная (или автоматная) грамматика — это грамматика с правилами подстановки вида или где А и В — переменные из , а — терминальный символ из . Альтернативными допустимыми правилами подстановки являются . Выбор одного из этих двух типов правил исключает, однако, применение правил другого типа.

Эти грамматики называют иногда грамматиками типа 0, 1, 2 и 3 соответственно. Кроме того, их часто обозначают как грамматики структуры составляющих.

Если каждое правило подстановки бесконтекстной грамматики имеет вид или , где А и В — нетерминальные символы, а и — терминальные цепочки, то грамматика считается линейной.

Интересно отметить, что все регулярные грамматики бесконтекстны, все бесконтекстные грамматики являются грамматиками непосредственно составляющих, а все грамматики непосредственно составляющих — неограниченны.

Пример. Способы функционирования обсуждаемых грамматик показаны на следующих простых примерах грамматик.

(а) Неограниченная грамматика

при

порождает предложения вида где означает длину цепочки символов. Например, для порождения цепочки мы применяем первые четыре правила

(кликните для просмотра скана)

Как и предполагалось, неограниченные грамматики обладают значительно большей мощностью, чем грамматики трех остальных типов. Однако степень общности этих грамматик создает ряд серьезных трудностей в их теоретических и практических приложениях. Это утверждение верно и для грамматик непосредственно составляющих.

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