Соглашения.

1. Терминалы будем обозначать строчными буквами из начала латинского алфавита или цифрами, а нетерминалы – заглавными латинскими буквами. Цепочки, содержащие как терминалы, так и нетерминалы, будем обозначать строчными греческим буквами, а цепочки, состоящие только из терминалов, обозначим строчными буквами из конца латинского алфавита (от u до z).

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

3. Для обозначения n правил с одинаковыми левыми частями , …, часто используют сокращенную запись .

Пример. Грамматикой является четверка G₁=({A, S}, {0, 1}, P, S), где P состоит из правил: , , (выписываются столбиком). Нетерминальными символами являются A и S, а терминальными – 0 и 1.

Грамматика определяет язык рекурсивным образом. Рекурсивность проявляется в задании особого рода цепочек, называемых выводимыми цепочками грамматики G=<N, T, P, S>:

(1) S – выводимая цепочка,

(2) Если для некоторых слов a, b, g, d из алфавита j=abg – выводимая цепочка и содержится в Р, то q=adg – тоже выводимая цепочка. При этом пишут и говорят, что цепочка q непосредственно выводима из цепочки j.

Замечание. Когда из контекста ясно, о какой грамматике идет речь, вместо можно писать просто Þ.

Пример. Пусть G=({S}, {a, b, c}, P, S), где . Тогда .

Если , то пишем и говорим, что цепочка выводима из цепочки . При этом последовательность слов , , …, называется выводом слова из в грамматике G. Число n называется длиной (количеством шагов) этого вывода. В частности, для всякого слова имеет место (так как возможен вывод длины 0).

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

Пример. Пусть G=({S}, {a, b}, P, S), где . Тогда . Длина этого вывода равна 4.

Через будем обозначать k-ую степень отношения Þ. Иначе говоря, , если существует последовательность , …, , состоящая из k цепочек (не обязательно различных), для которых при и . Эта последовательность цепочек называется выводом длины k цепочки b из цепочки a₀ в грамматике G.

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

Замечание. Существенно, что в определение грамматики включены 2 алфавита – T и N. Это позволило нам в определении языка, порождаемого грамматикой, отсеять часть слов, получаемых из начального символа. А именно, отбрасывается каждое слово, содержащее хотя бы один символ, не принадлежащий алфавиту Т.

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

Примеры грамматик.

1. Пусть G₁=({A, S}, {0, 1}, P, S), где P={ , , }. Рассмотрим вывод . Теперь очевидно, что .

2. Пусть G₀=({S, E, F}, {a, +, ´, (,)}, P, S), где

. Пример вывода в этой грамматике:

.

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