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

Определения

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

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

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

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

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

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

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

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

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

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

Обозначения

• Нетерминалы обозначаются заглавными буквами латинского алфавита (например: $A, B, C$).
• Терминалы обозначаются строчными буквами из начала латинского алфавита (например: $a, b, c$).
• Последовательности из терминалов (слова) обозначают строчными буквами из конца латинского или греческого алфавита (например: $\omega$).
  
• Последовательности из терминалов и нетерминалов обозначаются строчными буквами из начала греческого алфавита (например: $\beta, \alpha$).

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

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

$\Sigma = \{(, )\}$
$\begin{array}{lcr} S \to (S) \\ S \to SS \\ S \to \varepsilon \end{array}$

Вывод строки $(()())$:
$S\Rightarrow(\boldsymbol{S})\Rightarrow(\boldsymbol{S}S)\Rightarrow((S)\boldsymbol{S})\Rightarrow((\boldsymbol{S})(S))\Rightarrow(()(\boldsymbol{S}))\Rightarrow(()())$.

Вывод строки $((()())(()))$:
$S\Rightarrow(\boldsymbol{S})\Rightarrow(\boldsymbol{S}S)\rightarrow((S)\boldsymbol{S})\rightarrow((\boldsymbol{S})(S))\rightarrow$$\rightarrow((\boldsymbol{S}S)((S)))\rightarrow (((\boldsymbol{S})S)((S))) \rightarrow ((()\boldsymbol{S})((S)))\rightarrow$
$\rightarrow((()(\boldsymbol{S}))((S)))\rightarrow ((()())((\boldsymbol{S})))\rightarrow ((()())(()))$.

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

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

$\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}$

Вывод строки $2+2*2$: $S \Rightarrow SO\boldsymbol{S} \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$.

Левосторонний вывод этой же строки: $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$.

Язык $0^n1^n2^n$

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

$\Sigma = \{0, 1, 2\}$

$S \rightarrow 012 \\ S \rightarrow 0TS2 \\ T0 \rightarrow 0T \\ T1 \rightarrow 11$

Вывод строки $000111222$ :

$S \Rightarrow 0T\boldsymbol{S} 2 \Rightarrow 0T0T\boldsymbol{S}22 \Rightarrow 0T\boldsymbol{0T}01222 \Rightarrow 0\boldsymbol{T0}0T1222 \Rightarrow 00\boldsymbol{T0}T1222 \Rightarrow 000T\boldsymbol{T1}222 \Rightarrow 000\boldsymbol{T1}1222 \Rightarrow 000111222$

Данная грамматика описывает этот язык, так как мы можем вывести любую строку одним методом. $n-1$ раз выполняем правило вывода $S \rightarrow 0TS2$. Потом выполняем правило $S \rightarrow 012$, $n-1$ раз выполняем $T0 \rightarrow 0T$. После этого у нас получается строка $0^nT^{n-1}2^n$. Выполняем $n-1$ раз последнее правило и в результате получаем искомую строку.

См. также

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

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

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