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

Материал из Викиконспекты
Перейти к: навигация, поиск
(ссылка на алфавит исправлена)
(Исправлено определение P)
Строка 7: Строка 7:
 
|definition =  
 
|definition =  
 
'''Формальная грамматика''' - это способ описания формального языка, представляющий собой четверку
 
'''Формальная грамматика''' - это способ описания формального языка, представляющий собой четверку
<tex>\Gamma =\langle \Sigma, N, S \in N, P \in 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 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>
 
}}
 
}}
  

Версия 03:44, 10 ноября 2011

Определение:
Нетерминал - элемент, представляющий некоторую сущность языка (например часть формулы) и не имеющий конкретного значения.


Определение:
Формальная грамматика - это способ описания формального языка, представляющий собой четверку [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]\Sigma[/math]


Определение:
[math]\alpha \Rightarrow \beta[/math] ([math]\beta[/math] выводится из [math]\alpha[/math] за один шаг), если

[math]\alpha=\alpha_1\alpha_2\alpha_3[/math]

[math]\beta=\beta_1\beta_2\beta_3[/math]

[math]\alpha_1=\beta1[/math]

[math]\alpha_3=\beta3[/math]

[math]\alpha_2\rightarrow\beta2 \in P[/math]


Определение:
[math]\alpha \Rightarrow^* \beta[/math] ([math]\beta[/math] выводится из [math]\alpha[/math] за ноль или более шагов), если [math]\alpha \Rightarrow \gamma_1 \Rightarrow \gamma_2 \Rightarrow ... \Rightarrow \gamma_n \Rightarrow \beta[/math]


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


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

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

[math]S \rightarrow (S)[/math]

[math]S \rightarrow SS[/math]

[math]S \rightarrow \epsilon[/math]

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

Арифметические выражения

[math]\Sigma = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, *, /, -, (, )}[/math]

[math]S \rightarrow S O S[/math]

[math]S \rightarrow (S) [/math]

[math]O \rightarrow + | - | * | /[/math]

[math]S \rightarrow (1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9) N[/math]

[math]S \rightarrow 0[/math]

[math]N \rightarrow NN[/math]

[math]N \rightarrow \epsilon[/math]

[math]N \rightarrow 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0[/math]