Математическая теория формальных языков
Порождающие грамматики
Определение 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 называется длиной
(количеством шагов) этого вывода.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий