313
правок
Изменения
Нет описания правки
|definition =
'''<tex>\beta</tex> выводится из <tex>\alpha</tex> за один шаг''' <tex>(\alpha \Rightarrow \beta)</tex>:
# <tex>\alpha=\alpha_1\alpha_2\alpha_3</tex>;# <tex>\beta=\beta_1\beta_2\beta_3</tex>;
# <tex>\alpha_1=\beta_1</tex>, <tex>\alpha_3=\beta_3</tex>, <tex>\alpha_2\rightarrow\beta_2 \in P</tex>.
}}
==Примеры грамматик==
===Правильные скобочные последовательности===
<tex>\Sigma = \{(, )\}</tex>;
<br/>
<tex>\begin{array}{lcr}
===Арифметические выражения===
<tex>\Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, *, /, -, (, )\}</tex>;
<br/>
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.
Данный язык является [[Иерархия Хомского формальных грамматик#Класс 1 |контекстно-зависимым]]. КЗ-грамматика для языка приведена ниже, а через [[Лемма о разрастании для КС-грамматик#Пример доказательства неконтекстно-свободности языка с использованием леммы | лемму о разрастании]] доказывается его неконтекстно-свободность.
<tex>\Sigma = \{0, 1, 2\}</tex>;
<tex>
