Определение.

Выводимость. Если имеется последовательность цепочек Х₀, Х₁ ,..., Х_n, в ко­торой каждая следующая цепочка непосредственно выводима из предыдущей, то це­почка Х_n выводима из цепочки Х₀. Последовательность цепочек Х₀, Х₁, ..., Х_n называ­ется выводом Х_n изХ₀—в грамматике G.

Существенно, что порождающая грамматика не есть алгоритм, поскольку пра­вила подстановки представляют собой не последовательность предписаний, а сово­купность решений. Это означает, что, во-первых, правило вида а → b понимается в грамматике как «а можно заменить на b» (но можно и не заменять); в алгоритме же а → b означало бы «а следует заменить на b» (нельзя не заменять); во-вторых, поря­док применения правил в грамматике произволен: любое правило, в принципе, раз­решается применять после любого.

Определение.

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

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

Определение.

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

Пусть алфавит символов (непустое конечное множество), из которых строятся цепочки языка L, представляет собой алфавит терминальных символов V_Т. Очевидно, что L ≤ V_Т *.

Определение формальной грамматики требует наличия еще одного алфавита V_N – непустого конечного множества нетерминальных символов (V_N ∧ V_Т = 0). Объединение этих алфавитов назовем словарем формального языка L: V = V_N ∨ V_Т.

Условимся обозначать элементы алфавита V_Т строчными латинскими буквами, элементы множества V_N – прописными латинскими буквами, элементы словаря V*, (цепочки символов словаря) – греческими буквами.

Определим также множество упорядоченных пар (полутуэвских соотношений) следующим образом:

П = {(α, β) | α ∈ V* V_N V* ∧ β ∈ V+}.

Каждая пара (α, β) называется продукцией и обозначается как α → β.

Заметим, что β является элементом усеченной итерации словаря, поэтому среди продукций нет пар вида α → ε, где ε – пустая цепочка.

Определение.

Формальная грамматика G – это совокупность четырех объектов (четвёрка): G = (V_T, V_N, P, S),

где V_Т – алфавит терминальных символов (множество основных понятий языка);

V_N – непустое конечное множество нетерминальных символов (вспомогательных понятий – обозначений конкретных классов слов, например, глаголов или предлогов, слогов, букв);

Р – непустое конечное подмножество продукций (П) – полутуэвская система подстановок;

S ∈ V_N – множества начальных символов.

Определение.

Языком L(G), порождаемым грамматикой G, будем называть множество цепочек α ∈ V_Т , каждая из которых порождается из начального символа S в смысле полутуэвских соотношений Р данной грамматики. Другими словами, L(G) = {α | α ∈ V_T* ∧ S ⇒ *α}.

4. Классификация формальных языков по Хомскому.

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

Типы грамматик по Хомскому располагаются по убыванию сложности языка и обозначают: тип 0, тип 1, тип 2 и тип 3.

Соответствующий тип грамматики определяется теми ограничениями, которые налагаются на продукцию Р.

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

Определение.

Если никаких ограничений нет, то грамматика принадлежит к типу 0 — грамматика без ограничений.

Определение.

Ограничение, налагаемое на длину цепочек α и β: | α | ≤ | β |, относит грамматики к типу 1. Такие грамматики также называют контекстно-зависимыми, то есть грамматиками непосредственных составляющих (НС-грамматиками).

Определение.

В том случае, когда цепочка α состоит из одного символа, т. е. α ∈ V_N, грамматики относят к типу 2. В этом случае их называют бесконтекстными (контекстно-свободными или КС-грамматиками).

Определение.

Регулярными грамматиками (типа 3) называют такие, для которых α ∈ V_N , а β ∈ V_ТV_N, либо β ∈ V_Т. Иными словами, правые части продукций регулярных грамматик состоят либо из одного терминального и одного нетерминального символов, либо из одного терминального символа.

Нетрудно видеть, что каждая регулярная грамматика является бесконтекстной, а каждая бесконтекстная грамматика является контекстно-зависимой. В свою очередь, каждая контекстно-зависимая грамматика – это грамматика типа 0. Обратное утверждение неверно.

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

С другой стороны, типы языков могут быть определены типами абстрактных распознающих устройств (автоматов). При этом язык определяется как множество цепочек, допускаемых распознающим устройством определенного типа. На рис. 3.1 приведена иерархия языков и соответствующие ей иерархии грамматик и автоматов как распознающих устройств. Любое множество, порождаемое автоматическим устройством произвольного вида, порождается некоторой грамматикой типа 0 по Хомскому.

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

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

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