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

Определения

Определение:

Формальная грамматика (англ. Formal grammar) — способ описания формального языка, представляющий собой четверку [math]\Gamma =\langle \Sigma, N, S \in N, P \subset N^{+}\times (\Sigma\cup N)^{*}\rangle[/math], где [math]\Sigma[/math] — алфавит, элементы которого называют терминалами (англ. terminals), [math]N[/math] — множество, элементы которого называют нетерминалами (англ. nonterminals), [math]S[/math] — начальный символ грамматики (англ. start symbol), [math]P[/math] — набор правил вывода (англ. production rules или productions) [math]\alpha\rightarrow \beta[/math].

Определение:

[math]\beta[/math] выводится из [math]\alpha[/math] за один шаг [math](\alpha \Rightarrow \beta)[/math]: [math]\alpha=\alpha_1\alpha_2\alpha_3[/math] [math]\beta=\beta_1\beta_2\beta_3[/math] [math]\alpha_1=\beta_1[/math], [math]\alpha_3=\beta_3[/math], [math]\alpha_2\rightarrow\beta_2 \in P[/math].

Определение:

[math]\beta[/math] выводится из [math]\alpha[/math] за ноль или более шагов [math](\alpha \Rightarrow^* \beta)[/math]: [math]\exists \gamma_1, \gamma_2, \ldots,\gamma_n : \alpha \Rightarrow \gamma_1 \Rightarrow \gamma_2 \Rightarrow \ldots \Rightarrow \gamma_n \Rightarrow \beta[/math] ( Рефлексивно-транзитивное замыкание отношения [math]\Rightarrow[/math]).

Определение:

Языком грамматики (англ. Language of grammar) называется [math]L(\Gamma) = \{\omega \in \Sigma^{*} \mid S \Rightarrow^{*}\omega\}[/math].

Определение:

Сентенциальная форма (англ. Sentential form) — последовательность терминалов и нетерминалов, выводимых из начального символа.

Обозначения

• Нетерминалы обозначаются заглавными буквами латинского алфавита.
• Терминалы обозначаются строчными буквами из начала латинского алфавита.
• Последовательности из терминалов (слова) обозначают строчными буквами из конца латинского или греческого алфавита.
  
• Последовательности из терминалов и нетерминалов обозначаются строчными буквами из начала греческого алфавита.

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

Правильные скобочные последовательности

[math]\Sigma = \{(, )\}[/math]
[math]\begin{array}{lcr} S \to (S) \\ S \to SS \\ S \to \varepsilon \end{array} [/math]

Вывод строки [math](()())[/math]:
[math]S\to(S)\to(SS)\to((S)S)\to((S)(S))\to(()(S))\to(()())[/math].

Вывод строки [math]((()())(()))[/math]:
[math]S\to(S)\to(SS)\rightarrow((S)S)\rightarrow((S)(S))\rightarrow[/math]
[math]\rightarrow((SS)((S)))\rightarrow (((S)S)((S))) \rightarrow ((()S)((S)))\rightarrow[/math]
[math]\rightarrow((()(S))((S)))\rightarrow ((()())((S)))\rightarrow ((()())(()))[/math].

Арифметические выражения

[math]\Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, *, /, -, (, )\}[/math]

[math]\begin{array}{lcr} S \rightarrow S O S\\ S \rightarrow (S)\\ S \rightarrow 0\\ S \rightarrow DN\\ O \rightarrow + \mid - \mid * \mid /\\ D \rightarrow 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9\\ N \rightarrow NN \mid \varepsilon\\ N \rightarrow 0 \mid 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9. \end{array} [/math]

Вывод строки [math]2+2*2[/math]: [math]S \Rightarrow S\boldsymbol{OS} \Rightarrow \boldsymbol{S} OSOS \Rightarrow 2O \boldsymbol{S} OS \Rightarrow 2O2O \boldsymbol{S} \Rightarrow 2 \boldsymbol{O} 2O2 \Rightarrow 2+2\boldsymbol{O}2 \Rightarrow 2+2*2[/math].

Левосторонний вывод этой же строки: [math]S \Rightarrow \boldsymbol{S}OS \Rightarrow 2\boldsymbol{O}S \Rightarrow 2+\boldsymbol{S} \Rightarrow 2+\boldsymbol{S}OS \Rightarrow 2+2\boldsymbol{O}S \Rightarrow 2+2*\boldsymbol{S} \Rightarrow 2+2*2[/math].

Язык [math]0^n1^n2^n[/math]

Данный язык является контекстно-зависимым. КЗ-грамматика для языка приведена ниже, а через лемму о разрастании доказывается его неконтекстно-свободность.

[math]\Sigma = \{0, 1, 2\}[/math]

[math] $S $ \rightarrow 012 \\ $S $ \rightarrow 0$TS$2 \\ $T$0 \rightarrow 0$T$ \\ $T$1 \rightarrow 11 [/math]

Вывод строки [math]000111222[/math] :

[math] $S $ \Rightarrow 0$TS$2 \Rightarrow 0$T0TS$22 \Rightarrow 0$T0T$01222 \Rightarrow 0$T00T1$222 \Rightarrow \\ \Rightarrow 00$T0T$1222 \Rightarrow 000$TT$1222 \Rightarrow 000$T$11222 \Rightarrow 000111222. [/math]

См. также

• Возможность порождения формальной грамматикой произвольного перечислимого языка
• Иерархия Хомского формальных грамматик
• Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
• Правоконтекстные грамматики, эквивалентность автоматам

Источники информации

• Wikipedia — Formal grammar
• Wikipedia — Formal language
• Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)