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

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

Тип 0. (формальные грамматики с фразовой структурой, неограниченные)

Грамматика G = (V_T, V_N,P, S) называется грамматикой типа 0, если на ее правила вывода не накладывается никаких ограничений, кроме тех, которые указаны в определении грамматики. Любое правило α→β может быть построено с использованием произвольных цепочек α, β(VTVN). Этот тип грамматик самый общий, включающий все грамматики. Однако некоторые грамматики могут принадлежать только к этому типу. Практического применения в силу своей сложности такие грамматики не имеют. Например: P = TR→HT или abC→xDa.

Тип 1. (контекстно-зависимые, контекстные грамматики, грамматика непосредственно составляющих, НС-грамматика)

К этому типу относятся контекстно-зависимые (КЗ) грамматики и неукорачивающие грамматики.

Грамматика G = (V_T,V_N,P,S) называется контекстно-зависимой грамматикой (КЗ-грамматикой), если каждое правило вывода из множества Р имеет вид αAβ→αγβ, где α, β∈V*, γ∈V⁺, A∈VN.

Грамматика G = (V_T,V_N,P,S) называется неукорачивающий грамматикой, если каждое правило вывода из множества Р имеет вид αAβ→αγβ, где α, β∈V*, γ∈V⁺, A∈VN и |A|<=|γ|.

Эти классы грамматик эквивалентны. Могут использоваться при анализе текстов на естественных языках, однако при построении компиляторов практически не используются в силу своей сложности. Для контекстно-зависимых грамматик доказано утверждение: по некоторому алгоритму за конечное число шагов можно установить, принадлежит цепочка терминальных символов данному языку или нет.

Тип 2. (Контекстно-свободной грамматикой, КС-грамматикой, бесконтекстной грамматикой)

Грамматика G = (V_T,V_N,P,S) называется контекстно-свободной грамматикой (КС-грамматикой), если ее правила вывода имеют вид: A→β, где β∈V+ (для неукорачивающих КС-грамматик, β∈V* для укорачивающих), A∈VN. То есть грамматика допускает появление в левой части правила только нетерминального символа.

КС-грамматики широко применяются для описания синтаксиса компьютерных языков (программирования).

Тип 3. (регулярная, Р-грамматика, линейная)

К третьему типу относятся регулярные грамматики (автоматные) — самые простые из формальных грамматик. Они являются контекстно-свободными, но с ограниченными возможностями. Все регулярные грамматики могут быть разделены на два эквивалентных класса:

• Грамматика G = (V_T, V_N, Р, S) называется праволинейной, если ее правила вывода имеют вид A→γB или A→γ, где γ∈VT*, A, B∈VN

• Грамматика G = (V_T, V_N, Р, S) называется леволинейной, если ее правила вывода имеют вид A→Bγ или A→γ, где γ∈VT*, A, B∈VN.

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

Справедливы следующие соотношения:

• каждый регулярный язык является КС-языком, но существуют КС-языки, которые не являются регулярными, например:

L = {aⁿbⁿ | n > 0};

• каждый КС-язык является КЗ-языком, но существуют КЗ-языки, которые не являются КС-языками, например:

L = {aⁿbⁿcⁿ | n > 0};

• каждый КЗ-язык является языком типа 0 (т. е. рекурсивно перечислимым языком), но существуют языки типа 0, которые не являются КЗ-языками, например: язык, состоящий из записей самоприменимых алгоритмов Маркова в некотором алфавите.)

Из этого следует иерархия классов языков:

Тип 3 (Регулярные) ⊂ Тип 2 (КС) ⊂ Тип 1 (КЗ) ⊂ Тип 0

(Запись A ⊂ B означает, что A является собственным подклассом класса B.)

Рисунок - Соотношение типов формальных языков и грамматик Вывод: одна и та же грамматика может быть отнесена к нескольким типам.

Язык называется контекстным языком (контекстно-свободным языком, линейным языком, праволинейным языком), если он порождается некоторой контекстной грамматикой (соответственно контекстно-свободной грамматикой, линейной грамматикой, праволинейной грамматикой). Контекстно-свободные языки называются также алгебраическими языками.

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

Языки типа 3, которые называют автоматными языками, языками с конечным числом состояний, нашли широкое применение в исследовании электронных схем, а также в ряде других областей (например, исследование цепей Маркова).

Рис. Иерархия грамматик, языков и автоматов

Совокупность всех терминальных цепочек, т. е. цепочек, состоящих только из терминальных символов, выводимых из начального символа в грамматике G, называется языком, порожденным грамматикой G, и обозначается L(G). Следовательно, применение грамматики – это построение полных выводов, последние цепочки которых и образуют язык, порожденный грамматикой.

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