Математическая теория формальных языков


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


Определение 1.4.1. Порождающей грамматикой (грамматикой типа 0, generative grammar, rewrite grammar) называется четверка , где N и - конечные алфавиты, , , P конечно и . Здесь - основной алфавит (терминальный алфавит), его элементы называются терминальными символами или терминалами (terminal), N - вспомогательный алфавит (нетерминальный алфавит), его элементы называются нетерминальными символами, нетерминалами, вспомогательными символами или переменными (nonterminal, variable), S - начальный символ (аксиома, start symbol). Пары

называются правилами подстановки, просто правилами или продукциями (rewriting rule, production) и записываются в виде .

Пример 1.4.2.

Пусть даны множества N = {S}, , . Тогда

является порождающей грамматикой.

Замечание 1.4.3.

Будем обозначать элементы множества

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

Замечание 1.4.4. Для обозначения n правил с одинаковыми левыми частями

часто используют сокращенную запись .

Определение 1.4.5. Пусть дана грамматика G. Пишем , если ,

и

для некоторых слов

в алфавите . Если , то говорят, что слово

непосредственно выводимо

из слова .

Замечание 1.4.6.

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

можно писать просто .

Пример 1.4.7. Пусть

Тогда .

Определение 1.4.8. Если , где , то пишем

и говорим, что слово

выводимо

из слова . Другими словами, бинарное отношение

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

При этом последовательность слов

называется выводом (derivation) слова

из слова

в грамматике G. Число n называется длиной

(количеством шагов) этого вывода.




Начало  Назад  Вперед



Книжный магазин