1632
правки
Изменения
м
<tex>\alpha \Rightarrow \beta</tex> ('''<tex>\beta</tex> выводится из <tex>\alpha</tex> за один шаг'''<tex>(\alpha \Rightarrow \beta)</tex>:
<tex>\alpha \Rightarrow^* \beta</tex> ('''<tex>\beta</tex> выводится из <tex>\alpha</tex> за ноль или более шагов'''<tex>(\alpha \Rightarrow^* \beta):<br/tex>:<tex>\exists \gamma_1, \gamma_2,...\ldots,\gamma_n : \alpha \Rightarrow \gamma_1 \Rightarrow \gamma_2 \Rightarrow ... \ldots \Rightarrow \gamma_n \Rightarrow \beta</tex>([[Транзитивное замыкание | Рефлексивно-транзитивное замыкание]] отношения <tex>\Rightarrow</tex>).
# <tex>S \rightarrow (Rightarrow 0T\boldsymbol{S} 2 \Rightarrow 0T0T\boldsymbol{S)}22 \Rightarrow 0T0\boldsymbol{T0}1222 \Rightarrow 0\boldsymbol{T0}0T1222 \Rightarrow 00\boldsymbol{T0}T1222 \Rightarrow 000T\boldsymbol{T1}222 \Rightarrow 000\boldsymbol{T1}1222 \Rightarrow 000111222</tex># Данная грамматика описывает этот язык, так как мы можем вывести любую строку одним методом. <tex>n-1</tex> раз выполняем правило вывода <tex>S \rightarrow SS0TS2 </tex># . Потом выполняем правило <tex>S \rightarrow 012 </tex>, <tex>n-1</tex> раз выполняем <tex>T0 \epsilonrightarrow 0T </tex>. После этого у нас получается строка <tex>0^nT^{n-1}2^n</tex>. Выполняем <tex>n-1</tex>раз последнее правило и в результате получаем искомую строку.
Вывод строки <tex>(()())</tex>:== См. также ==<tex>S\rightarrow(S)\rightarrow(SS)\rightarrow((S)S)\rightarrow((S)(S))\rightarrow(()(S))\rightarrow(()())</tex>* [[Возможность_порождения_формальной_грамматикой_произвольного_перечислимого_языка|Возможность порождения формальной грамматикой произвольного перечислимого языка]]* [[Иерархия Хомского формальных грамматик|Иерархия Хомского формальных грамматик]]* [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]* [[Правоконтекстные грамматики, эквивалентность автоматам|Правоконтекстные грамматики, эквивалентность автоматам]]
Вывод строки <tex>2+2*2</tex>: <tex>S \rightarrow SOS \rightarrow SOSOS \rightarrow 2OSOS \rightarrow 2O2OS \rightarrow 2O2O2 \rightarrow 2+2O2 \rightarrow 2+2*2</tex>
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Левосторонний вывод]] для такой же строки: <tex>S \rightarrow SOS \rightarrow 2OS \rightarrow 2+S \rightarrow 2+SOS \rightarrow 2+2OS \rightarrow 2+2*S \rightarrow 2+2*2</tex>
= Литература =[[Категория: Теория формальных языков]]* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2[[Категория: Контекстно-е изд. свободные грамматики]][[Категория: Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)Базовые понятия о грамматиках]]
rollbackEdits.php mass rollback
== Определения ={{Определение|definition ='''Нетерминал''' — элемент, представляющий некоторую сущность языка (например, часть формулы) и не имеющий конкретного значения.<br/>}} {{Определение|definition ='''Терминал''' — элемент [[Основные_определения: алфавит, слово, язык, конкатенация, свободный моноид слов|алфавита]] <tex>\Sigma</tex>. <br/>}}
{{Определение
|definition =
'''Формальная грамматика''' (англ. ''Formal grammar'') — способ описания формального языка, представляющий собой четверку<tex>\Gamma =\langle \Sigma, N, S \in N, P \subset ((\Sigma \cup N)^{+}* N (\Sigma \cup N)^*) \times (\Sigma\cup N)^{*}\rangle</tex>, где :* <tex>\Sigma</tex> — [[Основные_определения: алфавит, слово, язык, конкатенация, свободный моноид слов|алфавит]], элементы которого называют '''терминалами''' (англ. ''terminals'');* <tex>N</tex> — набор нетерминаловмножество, элементы которого называют '''нетерминалами''' (англ. ''nonterminals'');* <tex>S</tex> — начальный символ грамматики, (англ. ''start symbol'');* <tex>P</tex> — набор правил вывода (англ. ''production rules'' или ''productions'') <tex>\alpha\rightarrow \beta</tex>.
}}
{{Определение
|definition =
# <tex>\alpha=\alpha_1\alpha_2\alpha_3</tex>
# <tex>\beta=\beta_1\beta_2\beta_3</tex>
# <tex>\alpha_1=\beta1beta_1</tex>, <tex>\alpha_3=\beta3beta_3</tex>, <tex>\alpha_2\rightarrow\beta2 beta_2 \in P</tex>.
}}
{{Определение
|definition =
}}
{{Определение
|definition =
'''Язык Языком грамматики''' — все последовательности терминалов, которые можно получить из начального символа по правилам вывода(англ. ''Language of grammar'') называется <tex>L(\Gamma) = \{\omega|S \Rightarrowin \Sigma^{*}\omega, mid S \omega \in \SigmaRightarrow^{*}\omega\}</tex>.}} {{Определение|id=sform|definition = '''Сентенциальная форма''' (англ. ''Sentential form'') — последовательность терминалов и нетерминалов, выводимых из начального символа.
}}
== Обозначения ==* Нетерминалы обозначаются заглавными буквами латинского алфавита(например: <tex>A, B, C</tex>).* Терминалы обозначаются строчными буквами из начала латинского алфавита(например: <tex>a, b, c</tex>).* Последовательности из терминалов (слова) обозначают строчными буквами из конца латинского или греческого алфавита(например: <tex>\omega</tex>).<br/>* Последовательности из терминалов и нетерминалов обозначаются строчными буквами из начала греческого алфавита(например: <tex>\beta, \alpha</tex>).
==Примеры грамматик=====Правильные скобочные последовательности===
<tex>\Sigma = \{(, )\}</tex>
<br/>
<tex>\begin{array}{lcr}
S \to (S) \\
S \to SS \\
S \to \varepsilon
\end{array}
</tex>
Вывод строки <tex>(()())</tex>:<br/>
<tex>S\Rightarrow(\boldsymbol{S})\Rightarrow(\boldsymbol{S}S)\Rightarrow((S)\boldsymbol{S})\Rightarrow((\boldsymbol{S})(S))\Rightarrow(()(\boldsymbol{S}))\Rightarrow(()())</tex>.
Вывод строки <tex>((()())(()))</tex>:<br/>
<tex>S\Rightarrow(\boldsymbol{S})\Rightarrow(\boldsymbol{S}S)\rightarrow((S)\boldsymbol{S})\rightarrow((\boldsymbol{S})(S))\rightarrow</tex><tex>\rightarrow((\boldsymbol{S}S)((S)))\rightarrow (((\boldsymbol{S})S)((S))) \rightarrow ((()\boldsymbol{S})((S)))\rightarrow</tex><br/><tex>\rightarrow((()(\boldsymbol{S}))((S)))\rightarrow ((()())((\boldsymbol{S})))\rightarrow ((()())(()))</tex>.
===Арифметические выражения===
<tex>\Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, *, /, -, (, )\}</tex>
<br/>
<tex>\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}
</tex><br/>
Вывод строки <tex>2+2*2</tex>: <tex>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</tex>.
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Левосторонний вывод]] этой же строки: <tex>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</tex>.
===Язык <tex>0^n1^n2^n</tex>===
Данный язык является [[Иерархия Хомского формальных грамматик#Класс 1 |контекстно-зависимым]]. КЗ-грамматика для языка приведена ниже, а через [[Лемма о разрастании для КС-грамматик#Пример доказательства неконтекстно-свободности языка с использованием леммы | лемму о разрастании]] доказывается его неконтекстно-свободность.
<tex>\Sigma = \{0, 1, 2\}</tex>
<tex>
S \rightarrow 012 \\
S \rightarrow 0TS2 \\
T0 \rightarrow 0T \\
T1 \rightarrow 11
</tex>
Вывод строки <tex>000111222</tex> :
==Арифметические выраженияИсточники информации==<tex>\Sigma = \* [[wikipedia:Formal_grammar | Wikipedia {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, ---}} Formal grammar]]*, /, [[wikipedia:Formal_language_theory | Wikipedia {{---, (, )\}</tex>} Formal language]]# <tex>S \rightarrow S O S</tex> — два выражения* ''Хопкрофт Д., Мотвани Р., соединенные действием# <tex>S \rightarrow (S) </tex> Ульман Д.'' — выражениеВведение в теорию автоматов, взятое в скобки# <tex>S \rightarrow 0</tex> — ноль# <tex>S \rightarrow DN</tex> — числоязыков и вычислений, у которого первая цифра не ноль# <tex>O \rightarrow + | 2- | * | /</tex> е изд. : Пер. с англ. — действие# <tex>D \rightarrow 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9</tex> — цифраМосква, Издательский дом «Вильямс», не являющаяся нулем# <tex>N \rightarrow NN | \epsilon</tex> 2002. — любая последовательность из цифр, возможно пустая# <tex>N \rightarrow 0 | 1 | 2 | 3 | 528 с. : ISBN 5-8459-0261-4 | 5 | 6 | 7 | 8 | 9</tex> — любая цифра(рус.)
