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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определения)
Строка 32: Строка 32:
 
}}
 
}}
  
= Обозначения =
+
== Обозначения ==
 
* Нетерминалы обозначаются заглавными буквами латинского алфавита.
 
* Нетерминалы обозначаются заглавными буквами латинского алфавита.
 
* Терминалы обозначаются строчными буквами из начала латинского алфавита.
 
* Терминалы обозначаются строчными буквами из начала латинского алфавита.
Строка 38: Строка 38:
 
* Последовательности из терминалов и нетерминалов обозначаются строчными буквами из начала греческого алфавита.
 
* Последовательности из терминалов и нетерминалов обозначаются строчными буквами из начала греческого алфавита.
  
=Примеры грамматик=
+
==Примеры грамматик==
==Правильные скобочные последовательности==
+
===Правильные скобочные последовательности===
 
<tex>\Sigma = \{(, )\}</tex>;
 
<tex>\Sigma = \{(, )\}</tex>;
 
<br/>
 
<br/>
Строка 76: Строка 76:
 
[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Левосторонний вывод]] этой же строки: <tex>S \rightarrow SOS \rightarrow 2OS \rightarrow 2+S \rightarrow 2+SOS \rightarrow 2+2OS \rightarrow  2+2*S \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 (рус.)
 
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Контекстно-свободные грамматики]]

Версия 19:32, 13 января 2014

Определения

Определение:
Формальная грамматика — способ описания формального языка, представляющий собой четверку [math]\Gamma =\langle \Sigma, N, S \in N, P \subset N^{+}\times (\Sigma\cup N)^{*}\rangle[/math], где [math]\Sigma[/math]алфавит, элементы которого называют терминалами, [math]N[/math] — множество, элементы которого называют нетерминалами, [math]S[/math] — начальный символ грамматики, [math]P[/math] — набор правил вывода [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,...,\gamma_n : \alpha \Rightarrow \gamma_1 \Rightarrow \gamma_2 \Rightarrow ... \Rightarrow \gamma_n \Rightarrow \beta[/math].


Определение:
Языком грамматики называется [math]L(\Gamma) = \{\omega \in \Sigma^{*}|S \Rightarrow^{*}\omega\}[/math].


Определение:
Сентенциальная форма — последовательность терминалов и нетерминалов, выводимых из начального символа.


Обозначения

  • Нетерминалы обозначаются заглавными буквами латинского алфавита.
  • Терминалы обозначаются строчными буквами из начала латинского алфавита.
  • Последовательности из терминалов (слова) обозначают строчными буквами из конца латинского или греческого алфавита.
  • Последовательности из терминалов и нетерминалов обозначаются строчными буквами из начала греческого алфавита.

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

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

[math]\Sigma = \{(, )\}[/math];
[math]\begin{array}{lcr} S \rightarrow (S);\\ S \rightarrow SS;\\ S \rightarrow \varepsilon. \end{array} [/math]

Вывод строки [math](()())[/math]:
[math]S\rightarrow(S)\rightarrow(SS)\rightarrow((S)S)\rightarrow((S)(S))\rightarrow(()(S))\rightarrow(()())[/math].

Вывод строки [math]((()())(()))[/math]:
[math]S\rightarrow(S)\rightarrow(SS)\rightarrow((S)S)\rightarrow((S)(S))\rightarrow[/math]
[math]\rightarrow((SS)((S)))\rightarrow (((S)S)((S))) \rightarrow ((()S)((S)))\rightarrow[/math]
[math]\rightarrow((()(S))((S)))\rightarrow ((()())((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 + | - | * | /;\\ D \rightarrow 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9;\\ N \rightarrow NN | \varepsilon;\\ N \rightarrow 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9. \end{array} [/math]

Вывод строки [math]2+2*2[/math]: [math]S \rightarrow SOS \rightarrow SOSOS \rightarrow 2OSOS \rightarrow 2O2OS \rightarrow 2O2O2 \rightarrow 2+2O2 \rightarrow 2+2*2[/math].

Левосторонний вывод этой же строки: [math]S \rightarrow SOS \rightarrow 2OS \rightarrow 2+S \rightarrow 2+SOS \rightarrow 2+2OS \rightarrow 2+2*S \rightarrow 2+2*2[/math].

Литература

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