Определения
| Определение: |
| Формальная грамматика (англ. 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] — начальный символ грамматики, [math]P[/math] — набор правил вывода(англ. production rules) [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,...,\gamma_n : \alpha \Rightarrow \gamma_1 \Rightarrow \gamma_2 \Rightarrow ... \Rightarrow \gamma_n \Rightarrow \beta[/math](рефлексивно-транзитивное замыкание отношения ([math]\alpha \Rightarrow \beta[/math]). |
| Определение: |
| Языком грамматики(англ. Language of grammar) называется [math]L(\Gamma) = \{\omega \in \Sigma^{*}|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 + | - | * | /\\
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}
[/math]
Вывод строки [math]2+2*2[/math]: [math]S \rightarrow SOS \rightarrow SOSOS \rightarrow 2OSOS \rightarrow 2O2OS \rightarrow 2O2O2 \rightarrow 2+2O2 \rightarrow 2+2*2[/math].
Левосторонний вывод этой же строки: [math]S \rightarrow SOS \rightarrow 2OS \rightarrow 2+S \rightarrow 2+SOS \rightarrow 2+2OS \rightarrow 2+2*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]
Литература
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
