Формальное определение грамматики

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

Определение. Грамматика - это четверка G = (N,T,P,S), где

(1) N - алфавит нетерминальных символов ;

(2) T - алфавит терминальных символов,

(3) P - конечное множество правил вида , где

(4) - начальный знак (или аксиома) грамматики.

Мы будем использовать большие латинские буквы для обозначения нетерминальных символов, малые латинские буквы из начала алфавита для обозначения терминальных символов, малые латинские буквы из конца алфавита для обозначения цепочек из и, наконец, малые греческие буквы для обозначения цепочек из .

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

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

Мы будем использовать также рефлексивно-транзитивное и транзитивное замыкания отношения , а также его степень (обозначаемые соответственно , и ). Если , то говорят, что цепочка выводима (нетривиально выводима, выводима за k шагов) из .

Если , то существует последовательность шагов

где и . Последовательность цепочек в этом случае называют выводом из

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

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

Грамматики G1 и G2 называются эквивалентными, если они порождают один и тот же язык, то есть

Пример 2.5. Грамматика G = ({S, B, C}, {a, b, c}, P, S), где , порождает язык

Действительно, применяем n - 1 раз правило 1 и получаем , затем один раз правило 2 и получаем , затем n(n - 1)/2 раз правило 3 и получаем .

Затем используем правило 4 и получаем aⁿbB^n-1Cⁿ. Затем применяем n - 1 раз правило 5 и получаем aⁿbⁿCⁿ. Затем применяем правило 6 и n - 1 раз правило 7 и получаем aⁿbⁿcⁿ. Можно показать, что язык L(G) состоит из цепочек только такого вида.

Пример 2.6. Рассмотрим грамматику . Легко видеть, что цепочка , так как существует вывод

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

Пример 2.7. Рассмотрим грамматику . Нетрудно показать, что грамматика порождает язык