Порождающие грамматики

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

Пусть А – конечное множество символов, называемое алфавитом;

А * – множество всех цепочек символов с элементами из А;

А* É{ e } – пустую цепочку.

Язык L над множеством А – это подмножество А *. L Í А *.

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

Порождающая грамматика задается четверкой объектов G = (V, A, R, a), где, R конечный набор правил подстановки вида

u ® v,

А – алфавит грамматики

V – конечное множество символов, содержащее алфавит А.

V *-множество цепочек символов, u, v Î V *.

a – начальный символ грамматики.

F Определение: Элементы из множества А называются терминальными (основными) символами, а элементы из множества (V – A) – нетерминальными (метасимволами).

Пусть j Î V *.

Рассмотрим цепочку символов y, которая порождается из цепочки символов j:

j Þ y Û j = j ₁ uj ₂,

y = j ₁ vj ₂ и существует правило u ® v.

F Определение: Порождаемый грамматикой язык L (G) состоит из тех последовательностей символов, которые в общем случае за несколько шагов могут быть порождены из начального символа и которые не содержат ни одного метасимвола.

Пусть a начальный метасимвол грамматики G = (V, A, R, a), тогда порождаемый этой грамматикой язык:

L (G)= { X: a Þ X Ç X Î A *}.

Последовательно ограничивая вид правил, можно построить 4-х ступенчатую иерархию грамматик из соответствующих им языков (иерархия Хомского):

Тип 0 (неограниченный). Разрешаются произвольные правила u ® v, где u Î V *\ A *, v Î V *

Тип 1 (Контекстно-зависимый). Разрешаются лишь правила, имеющие вид u ₁ b u ₂ ® u ₁ v u ₂, где u ₁, u ₂Î V *, b Î V \ A, v Î V *, v ¹ e.

Тип 2 (контекстно-свободный). Разрешаются правила вида b ® v, где b Î V \ A, v Î V *, v ¹ e.

Тип 3 (регулярные). Разрешаются лишь правила вида b ® c или b ® cd, где b, d Î V \ A, c Î A.

Для распознавания принадлежности той или иной цепочки языку, порождаемому грамматикой, строятся автоматы, называемые акцепторами или распознавателями. Каждой грамматике соответствует свой порождаемый ею язык, каждому языку – свой распознающий его автомат.