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

Сложность грамматики определяется ограничениями на порождающие правила. Если на правила не накладываются никакие дополнительные ограничения, то грамматика относится к классу 0, или к общему классу. Наложение все более строгих ограничений позволяет определить иерархию классов грамматик по убыванию сложности.

Грамматика относится к классу 1, если все порождающие правила имеют вид:

αAβ → αγβ,

где α и β – цепочки из терминальных и (или) нетерминальных символов, одна из них или они обе могут быть пустыми; A – нетерминальный символ, γ – цепочка из терминальных и (или) нетерминальных символов, она не должна быть пустой. Грамматика класса 1 имеет еще одно название – контекстно-зависимая грамматика (или сокращенно КЗ-грамматика), потому что при порождении нетерминал A заменяется цепочкой γ в контексте цепочек α и β. Таким образом, все правила КЗ-грамматики должны быть неукорачивающими.

Грамматика относится к классу 2, если все порождающие правила имеют вид:

A → γ,

где A – нетерминальный символ, γ – цепочка из терминальных и (или) нетерминальных символов. Грамматика класса 2 имеет еще одно название – бесконтекстная или контекстно-свободная грамматика (сокращенно КС-грамматика). В КС-грамматике допускаются правила, правая часть которых состоит из пустой цепочки, т.е. правила, которые являются укорачивающими.

Грамматика относится к классу 3, если все порождающие правила имеют вид:

A → aB или A → a,

где A,B – нетерминальные символы, а – терминальный символ. Грамматика класса 3 имеет еще одно название – автоматная грамматика (сокращенно А-грамматика).

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

ω₁αω₂,

такой, что α является такой самой левой частью всей цепочки, которая совпадает с левой частью какого-либо из правил грамматики. Пусть это правило: α → β, тогда после его применения получится цепочка:

ω₁βω₂.

Если на каждом шаге порождение применяется только таким образом, то оно называется левым каноническим.

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

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

Свойством однозначности или неоднозначности могут обладать грамматики любого класса: от общего класса 0 до А-грамматик класса 3.

Дата добавления: 2015-07-26; просмотров: 237; Нарушение авторских прав

Мы поможем в написании ваших работ!