Формальные грамматики — различия между версиями
Watson (обсуждение | вклад) (→Язык 0^n1^n2^n) |
м (rollbackEdits.php mass rollback) |
||
(не показано 69 промежуточных версий 8 участников) | |||
Строка 4: | Строка 4: | ||
|definition = | |definition = | ||
'''Формальная грамматика''' (англ. ''Formal grammar'') — способ описания формального языка, представляющий собой четверку | '''Формальная грамматика''' (англ. ''Formal grammar'') — способ описания формального языка, представляющий собой четверку | ||
− | <tex>\Gamma =\langle \Sigma, N, S \in N, P \subset N^ | + | <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 = | |definition = | ||
− | '''<tex>\beta</tex> выводится из <tex>\alpha</tex> за один шаг''' | + | '''<tex>\beta</tex> выводится из <tex>\alpha</tex> за один шаг''' <tex>(\alpha \Rightarrow \beta)</tex>: |
− | # <tex>\alpha=\alpha_1\alpha_2\alpha_3</tex> | + | # <tex>\alpha=\alpha_1\alpha_2\alpha_3</tex> |
− | # <tex>\beta=\beta_1\beta_2\beta_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>\alpha_1=\beta_1</tex>, <tex>\alpha_3=\beta_3</tex>, <tex>\alpha_2\rightarrow\beta_2 \in P</tex>. | ||
}} | }} | ||
Строка 17: | Строка 21: | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | '''<tex>\beta</tex> выводится из <tex>\alpha</tex> за ноль или более шагов''' | + | '''<tex>\beta</tex> выводится из <tex>\alpha</tex> за ноль или более шагов''' <tex>(\alpha \Rightarrow^* \beta)</tex>: |
− | <tex>\exists \gamma_1, \gamma_2, | + | <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>). |
}} | }} | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | '''Языком грамматики'''(англ. ''Language of grammar'') называется <tex>L(\Gamma) = \{\omega \in \Sigma^{*} | + | '''Языком грамматики''' (англ. ''Language of grammar'') называется <tex>L(\Gamma) = \{\omega \in \Sigma^{*} \mid S \Rightarrow^{*}\omega\}</tex>. |
}} | }} | ||
Строка 29: | Строка 33: | ||
|id=sform | |id=sform | ||
|definition = | |definition = | ||
− | '''Сентенциальная форма'''(англ. ''Sentential form'') — последовательность терминалов и нетерминалов, выводимых из начального символа. | + | '''Сентенциальная форма''' (англ. ''Sentential form'') — последовательность терминалов и нетерминалов, выводимых из начального символа. |
}} | }} | ||
== Обозначения == | == Обозначения == | ||
− | * Нетерминалы обозначаются заглавными буквами латинского алфавита. | + | * Нетерминалы обозначаются заглавными буквами латинского алфавита (например: <tex>A, B, C</tex>). |
− | * Терминалы обозначаются строчными буквами из начала латинского алфавита. | + | * Терминалы обозначаются строчными буквами из начала латинского алфавита (например: <tex>a, b, c</tex>). |
− | * Последовательности из терминалов (слова) обозначают строчными буквами из конца латинского или греческого алфавита.<br/> | + | * Последовательности из терминалов (слова) обозначают строчными буквами из конца латинского или греческого алфавита (например: <tex>\omega</tex>).<br/> |
− | * Последовательности из терминалов и нетерминалов обозначаются строчными буквами из начала греческого алфавита. | + | * Последовательности из терминалов и нетерминалов обозначаются строчными буквами из начала греческого алфавита (например: <tex>\beta, \alpha</tex>). |
==Примеры грамматик== | ==Примеры грамматик== | ||
===Правильные скобочные последовательности=== | ===Правильные скобочные последовательности=== | ||
− | <tex>\Sigma = \{(, )\}</tex> | + | <tex>\Sigma = \{(, )\}</tex> |
<br/> | <br/> | ||
<tex>\begin{array}{lcr} | <tex>\begin{array}{lcr} | ||
− | S \ | + | S \to (S) \\ |
− | S \ | + | S \to SS \\ |
− | S \ | + | S \to \varepsilon |
\end{array} | \end{array} | ||
− | </tex | + | </tex> |
Вывод строки <tex>(()())</tex>:<br/> | Вывод строки <tex>(()())</tex>:<br/> | ||
− | <tex>S\ | + | <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>((()())(()))</tex>:<br/> | ||
− | <tex>S\ | + | <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>\rightarrow(( | ||
===Арифметические выражения=== | ===Арифметические выражения=== | ||
− | <tex>\Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9 | + | <tex>\Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, *, /, -, (, )\}</tex> |
<br/> | <br/> | ||
<tex>\begin{array}{lcr} | <tex>\begin{array}{lcr} | ||
− | S \rightarrow S O S | + | S \rightarrow S O S\\ |
− | S \rightarrow (S) | + | S \rightarrow (S)\\ |
− | S \rightarrow 0 | + | S \rightarrow 0\\ |
− | S \rightarrow DN | + | S \rightarrow DN\\ |
− | O \rightarrow + | + | O \rightarrow + \mid - \mid * \mid /\\ |
− | D \rightarrow 1 | + | D \rightarrow 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9\\ |
− | N \rightarrow NN | + | N \rightarrow NN \mid \varepsilon\\ |
− | N \rightarrow 0 | + | N \rightarrow 0 \mid 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9. |
\end{array} | \end{array} | ||
</tex><br/> | </tex><br/> | ||
− | Вывод строки <tex>2+2*2</tex>: <tex>S \ | + | Вывод строки <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 \ | + | [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Левосторонний вывод]] этой же строки: <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>=== | ===Язык <tex>0^n1^n2^n</tex>=== | ||
+ | Данный язык является [[Иерархия Хомского формальных грамматик#Класс 1 |контекстно-зависимым]]. КЗ-грамматика для языка приведена ниже, а через [[Лемма о разрастании для КС-грамматик#Пример доказательства неконтекстно-свободности языка с использованием леммы | лемму о разрастании]] доказывается его неконтекстно-свободность. | ||
− | + | <tex>\Sigma = \{0, 1, 2\}</tex> | |
− | <tex>\Sigma = \{0, 1, 2\}</tex> | ||
<tex> | <tex> | ||
− | S \rightarrow 012 | + | S \rightarrow 012 \\ |
− | S \rightarrow 0TS2 | + | S \rightarrow 0TS2 \\ |
− | T0 \rightarrow 0T | + | T0 \rightarrow 0T \\ |
− | T1 \rightarrow 11. | + | T1 \rightarrow 11 |
− | </tex>< | + | </tex> |
+ | |||
+ | Вывод строки <tex>000111222</tex> : | ||
+ | |||
+ | <tex>S \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 0TS2 </tex>. Потом выполняем правило <tex>S \rightarrow 012 </tex>, <tex>n-1</tex> раз выполняем <tex>T0 \rightarrow 0T </tex>. После этого у нас получается строка <tex>0^nT^{n-1}2^n</tex>. Выполняем <tex>n-1</tex> раз последнее правило и в результате получаем искомую строку. | ||
+ | |||
+ | == См. также == | ||
+ | * [[Возможность_порождения_формальной_грамматикой_произвольного_перечислимого_языка|Возможность порождения формальной грамматикой произвольного перечислимого языка]] | ||
+ | * [[Иерархия Хомского формальных грамматик|Иерархия Хомского формальных грамматик]] | ||
+ | * [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]] | ||
+ | * [[Правоконтекстные грамматики, эквивалентность автоматам|Правоконтекстные грамматики, эквивалентность автоматам]] | ||
+ | |||
+ | == Источники информации== | ||
+ | * [[wikipedia:Formal_grammar | Wikipedia {{---}} Formal grammar]] | ||
+ | * [[wikipedia:Formal_language_theory | Wikipedia {{---}} Formal language]] | ||
+ | * ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.) | ||
+ | |||
− | |||
− | |||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
[[Категория: Контекстно-свободные грамматики]] | [[Категория: Контекстно-свободные грамматики]] | ||
+ | [[Категория: Базовые понятия о грамматиках]] |
Текущая версия на 19:27, 4 сентября 2022
Определения
Определение: |
Формальная грамматика (англ. Formal grammar) — способ описания формального языка, представляющий собой четверку
, где:
|
Определение: |
| выводится из за один шаг :
Определение: |
Рефлексивно-транзитивное замыкание отношения ). | выводится из за ноль или более шагов : (
Определение: |
Языком грамматики (англ. Language of grammar) называется | .
Определение: |
Сентенциальная форма (англ. Sentential form) — последовательность терминалов и нетерминалов, выводимых из начального символа. |
Обозначения
- Нетерминалы обозначаются заглавными буквами латинского алфавита (например: ).
- Терминалы обозначаются строчными буквами из начала латинского алфавита (например: ).
- Последовательности из терминалов (слова) обозначают строчными буквами из конца латинского или греческого алфавита (например:
- Последовательности из терминалов и нетерминалов обозначаются строчными буквами из начала греческого алфавита (например: ).
Примеры грамматик
Правильные скобочные последовательности
Вывод строки
.
Вывод строки
.
Арифметические выражения
Вывод строки
: .Левосторонний вывод этой же строки: .
Язык
Данный язык является контекстно-зависимым. КЗ-грамматика для языка приведена ниже, а через лемму о разрастании доказывается его неконтекстно-свободность.
Вывод строки
:
Данная грамматика описывает этот язык, так как мы можем вывести любую строку одним методом.
раз выполняем правило вывода . Потом выполняем правило , раз выполняем . После этого у нас получается строка . Выполняем раз последнее правило и в результате получаем искомую строку.См. также
Источники информации
- Wikipedia — Formal grammar
- Wikipedia — Formal language
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)