Формальные грамматики — различия между версиями
Watson (обсуждение | вклад) (→Примеры грамматик) |
Watson (обсуждение | вклад) (→Примеры грамматик) |
||
Строка 50: | Строка 50: | ||
Вывод строки <tex>(()())</tex>:<br/> | Вывод строки <tex>(()())</tex>:<br/> | ||
− | + | <tex>$S\to(S)\to(SS)\to((S)S)\to((S)(S))\to(()(S))\to(()())$</tex>. | |
Вывод строки <tex>((()())(()))</tex>:<br/> | Вывод строки <tex>((()())(()))</tex>:<br/> |
Версия 21:45, 13 января 2014
Содержание
Определения
Определение: |
Формальная грамматика (англ. Formal grammar) — способ описания формального языка, представляющий собой четверку алфавит, элементы которого называют терминалами(англ. terminals), — множество, элементы которого называют нетерминалами(англ. nonterminals), — начальный символ грамматики, — набор правил вывода(англ. production rules) . | , где —
Определение: |
| выводится из за один шаг ( ):
Определение: |
выводится из за ноль или более шагов ( ): . |
Определение: |
Языком грамматики(англ. Language of grammar) называется | .
Определение: |
Сентенциальная форма(англ. Sentential form) — последовательность терминалов и нетерминалов, выводимых из начального символа. |
Обозначения
- Нетерминалы обозначаются заглавными буквами латинского алфавита.
- Терминалы обозначаются строчными буквами из начала латинского алфавита.
- Последовательности из терминалов (слова) обозначают строчными буквами из конца латинского или греческого алфавита.
- Последовательности из терминалов и нетерминалов обозначаются строчными буквами из начала греческого алфавита.
Примеры грамматик
Правильные скобочные последовательности
Вывод строки
.
Вывод строки
.
Арифметические выражения
Вывод строки
: .Левосторонний вывод этой же строки: .
Язык
;
Данный язык является контекстно-зависимым. КЗ-грамматика для языка приведена выше, а через лемму о разрастании доказывается его неконтекстно-свободность.
Литература
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)