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

Определения

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

Формальная грамматика (англ. Formal grammar) — способ описания формального языка, представляющий собой четверку $\Gamma =\langle \Sigma, N, S \in N, P \subset N^{+}\times (\Sigma\cup N)^{*}\rangle$, где $\Sigma$ — алфавит, элементы которого называют терминалами(англ. terminals), $N$ — множество, элементы которого называют нетерминалами(англ. nonterminals), $S$ — начальный символ грамматики, $P$ — набор правил вывода(англ. production rules) $\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,...,\gamma_n : \alpha \Rightarrow \gamma_1 \Rightarrow \gamma_2 \Rightarrow ... \Rightarrow \gamma_n \Rightarrow \beta$.

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

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

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

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

Обозначения

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

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

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

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

Вывод строки $(()())$:
$$S$\to(S)\to(SS)\to((S)S)\to((S)(S))\to(()(S))\to(()())$.

Вывод строки $((()())(()))$:
$S\to(S)\to(SS)\rightarrow((S)S)\rightarrow((S)(S))\rightarrow$
$\rightarrow((SS)((S)))\rightarrow (((S)S)((S))) \rightarrow ((()S)((S)))\rightarrow$
$\rightarrow((()(S))((S)))\rightarrow ((()())((S)))\rightarrow ((()())(()))$.

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

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

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

Вывод строки $2+2*2$: $S \rightarrow SOS \rightarrow SOSOS \rightarrow 2OSOS \rightarrow 2O2OS \rightarrow 2O2O2 \rightarrow 2+2O2 \rightarrow 2+2*2$.

Левосторонний вывод этой же строки: $S \rightarrow SOS \rightarrow 2OS \rightarrow 2+S \rightarrow 2+SOS \rightarrow 2+2OS \rightarrow 2+2*S \rightarrow 2+2*2$.

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

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

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

$$S$ \rightarrow 012 \\ $S$ \rightarrow 0$TS$2 \\ $T$0 \rightarrow 0$T$ \\ $T$1 \rightarrow 11$

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

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

Литература

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