Формальные грамматики — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Маленькие фиксы)
м (rollbackEdits.php mass rollback)
 
(не показано 107 промежуточных версий 13 участников)
Строка 1: Строка 1:
{{Определение
+
== Определения ==
|definition =
 
'''Нетерминал''' — элемент, представляющий некоторую сущность языка (например, часть формулы) и не имеющий конкретного значения.<br/>
 
Нетерминалы обозначаются заглавными буквами латинского алфавита.
 
}}
 
 
 
{{Определение
 
|definition =
 
'''Терминал''' — элемент алфавита <tex>\Sigma</tex><br/>
 
Терминалы обозначаются строчными буквами латинского алфавита.
 
}}
 
 
 
Последовательности из терминалов и нетерминалов обозначаются строчными буквами греческого алфавита.
 
  
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
'''Формальная грамматика''' — способ описания формального языка, представляющий собой четверку
+
'''Формальная грамматика''' (англ. ''Formal grammar'') — способ описания формального языка, представляющий собой четверку
<tex>\Gamma =\langle \Sigma, N, S \in N, P \subset N^{+}\times (\Sigma\cup N)^{*}\rangle</tex>, где <tex>\Sigma</tex> - [[wiki:Основные_определения: алфавит, слово, язык, конкатенация, свободный моноид слов|алфавит]], <tex>N</tex> - набор нетерминалов, <tex>S</tex> - начальный символ грамматики, <tex>P</tex> - набор правил вывода <tex>\alpha\rightarrow \beta</tex>
+
<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>\alpha \Rightarrow \beta</tex> ('''<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=\beta1</tex>, <tex>\alpha_3=\beta3</tex>, <tex>\alpha_2\rightarrow\beta2 \in P</tex>
+
# <tex>\alpha_1=\beta_1</tex>, <tex>\alpha_3=\beta_3</tex>, <tex>\alpha_2\rightarrow\beta_2 \in P</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
<tex>\alpha \Rightarrow^* \beta</tex> ('''<tex>\beta</tex> выводится из <tex>\alpha</tex> за ноль или более шагов'''):<br/>
+
'''<tex>\beta</tex> выводится из <tex>\alpha</tex> за ноль или более шагов''' <tex>(\alpha \Rightarrow^* \beta)</tex>:
<tex>\exists \gamma_1, \gamma_2,...,\gamma_n : \alpha \Rightarrow \gamma_1 \Rightarrow \gamma_2 \Rightarrow ... \Rightarrow \gamma_n \Rightarrow \beta</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>).
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
   '''Язык грамматики''' — все последовательности терминалов, которые можно получить из начального символа по правилам вывода. <tex>L(\Gamma) = \{\omega|S \Rightarrow^{*}\omega, \omega \in \Sigma^{*}\}</tex>.
+
   '''Языком грамматики''' (англ. ''Language of grammar'')        называется <tex>L(\Gamma) = \{\omega \in \Sigma^{*} \mid S \Rightarrow^{*}\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>
 
<tex>\Sigma = \{(, )\}</tex>
 +
<br/>
 +
<tex>\begin{array}{lcr}
 +
S \to (S) \\
 +
S \to SS \\
 +
S \to \varepsilon
 +
\end{array}
 +
</tex>
  
# <tex>S \rightarrow (S)</tex>
+
Вывод строки <tex>(()())</tex>:<br/>
# <tex>S \rightarrow SS</tex>
+
<tex>S\Rightarrow(\boldsymbol{S})\Rightarrow(\boldsymbol{S}S)\Rightarrow((S)\boldsymbol{S})\Rightarrow((\boldsymbol{S})(S))\Rightarrow(()(\boldsymbol{S}))\Rightarrow(()())</tex>.
# <tex>S \rightarrow \epsilon</tex>
 
  
Вывод строки <tex>(()())</tex>:
+
Вывод строки <tex>((()())(()))</tex>:<br/>
<tex>S\rightarrow(S)\rightarrow(SS)\rightarrow((S)S)\rightarrow((S)(S))\rightarrow(()(S))\rightarrow(()())</tex>
+
<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, 0, +, *, /, -, (, )\}</tex>
+
<tex>\Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, *, /, -, (, )\}</tex>
# <tex>S \rightarrow S O S</tex> — два выражения, соединенные действием
+
<br/>
# <tex>S \rightarrow (S) </tex> — выражение, взятое в скобки
+
 
# <tex>S \rightarrow 0</tex> — ноль
+
<tex>\begin{array}{lcr}
# <tex>S \rightarrow DN</tex> — число, у которого первая цифра не ноль
+
S \rightarrow S O S\\
# <tex>O \rightarrow + | - | * | /</tex> — действие
+
S \rightarrow (S)\\
# <tex>D \rightarrow 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9</tex> — цифра, не являющаяся нулем
+
S \rightarrow 0\\
# <tex>N \rightarrow NN | \epsilon</tex> — любая последовательность из цифр, возможно пустая
+
S \rightarrow DN\\
# <tex>N \rightarrow 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9</tex> любая цифра
+
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>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 (рус.)
 +
 
  
Вывод строки <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>
+
[[Категория: Теория формальных языков]]
 +
[[Категория: Контекстно-свободные грамматики]]
 +
[[Категория: Базовые понятия о грамматиках]]

Текущая версия на 19:27, 4 сентября 2022

Определения

Определение:
Формальная грамматика (англ. Formal grammar) — способ описания формального языка, представляющий собой четверку

[math]\Gamma =\langle \Sigma, N, S \in N, P \subset ((\Sigma \cup N)^* N (\Sigma \cup 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]:
  1. [math]\alpha=\alpha_1\alpha_2\alpha_3[/math]
  2. [math]\beta=\beta_1\beta_2\beta_3[/math]
  3. [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]A, B, C[/math]).
  • Терминалы обозначаются строчными буквами из начала латинского алфавита (например: [math]a, b, c[/math]).
  • Последовательности из терминалов (слова) обозначают строчными буквами из конца латинского или греческого алфавита (например: [math]\omega[/math]).
  • Последовательности из терминалов и нетерминалов обозначаются строчными буквами из начала греческого алфавита (например: [math]\beta, \alpha[/math]).

Примеры грамматик

Правильные скобочные последовательности

[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, +, *, /, -, (, )\}[/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 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[/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] раз последнее правило и в результате получаем искомую строку.

См. также

Источники информации

  • Wikipedia — Formal grammar
  • Wikipedia — Formal language
  • Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)