Определения
| Определение: |
| Формальная грамматика (англ. 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\Rightarrow(\boldsymbol{S})\Rightarrow(\boldsymbol{S}S)\Rightarrow((S)\boldsymbol{S})\Rightarrow((\boldsymbol{S})(S))\Rightarrow(()(\boldsymbol{S}))\Rightarrow(()())[/math].
Вывод строки [math]((()())(()))[/math]:
[math]S\Rightarrow(\boldsymbol{S})\Rightarrow(\boldsymbol{S}S)\rightarrow((S)\boldsymbol{S})\rightarrow((\boldsymbol{S})(S))\rightarrow[/math][math]\rightarrow((\boldsymbol{S}S)((S)))\rightarrow (((\boldsymbol{S})S)((S))) \rightarrow ((()\boldsymbol{S})((S)))\rightarrow[/math]
[math]\rightarrow((()(\boldsymbol{S}))((S)))\rightarrow ((()())((\boldsymbol{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 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[/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 0TS2 \\
T0 \rightarrow 0T \\
T1 \rightarrow 11
[/math]
Вывод строки [math]000111222[/math] :
[math]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[/math]
Данная грамматика описывает этот язык, так как мы можем вывести любую строку одним методом. [math]n-1[/math] раз выполняем правило вывода [math]S \rightarrow 0TS2 [/math]. Потом выполняем правило [math]S \rightarrow 012 [/math], [math]n-1[/math] раз выполняем [math]T0 \rightarrow 0T [/math]. После этого у нас получается строка [math]0^nT^{n-1}2^n[/math]. Выполняем [math]n-1[/math] раз последнее правило и в результате получаем искомую строку.
См. также
Источники информации
