Редактирование: Формальные грамматики

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 4: Строка 4:
 
|definition =  
 
|definition =  
 
'''Формальная грамматика'''  (англ. ''Formal grammar'') — способ описания формального языка, представляющий собой четверку
 
'''Формальная грамматика'''  (англ. ''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>\Gamma =\langle \Sigma, N, S \in N, P \subset 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>.
* <tex>\Sigma</tex> — [[Основные_определения: алфавит, слово, язык, конкатенация, свободный моноид слов|алфавит]], элементы которого называют '''терминалами''' (англ. ''terminals'');
 
* <tex>N</tex> — множество, элементы которого называют '''нетерминалами''' (англ. ''nonterminals'');
 
* <tex>S</tex> — начальный символ грамматики (англ. ''start symbol'');
 
* <tex>P</tex> — набор правил вывода (англ. ''production rules'' или ''productions'')      <tex>\alpha\rightarrow \beta</tex>.
 
 
}}
 
}}
  
Строка 37: Строка 33:
  
 
== Обозначения ==
 
== Обозначения ==
* Нетерминалы обозначаются заглавными буквами латинского алфавита (например: <tex>A, B, C</tex>).
+
* Нетерминалы обозначаются заглавными буквами латинского алфавита.
* Терминалы обозначаются строчными буквами из начала латинского алфавита (например: <tex>a, b, c</tex>).
+
* Терминалы обозначаются строчными буквами из начала латинского алфавита.
* Последовательности из терминалов (слова) обозначают строчными буквами из конца латинского или греческого алфавита (например: <tex>\omega</tex>).<br/>
+
* Последовательности из терминалов (слова) обозначают строчными буквами из конца латинского или греческого алфавита.<br/>
* Последовательности из терминалов и нетерминалов обозначаются строчными буквами из начала греческого алфавита (например: <tex>\beta, \alpha</tex>).
+
* Последовательности из терминалов и нетерминалов обозначаются строчными буквами из начала греческого алфавита.
  
 
==Примеры грамматик==
 
==Примеры грамматик==
Строка 54: Строка 50:
  
 
Вывод строки <tex>(()())</tex>:<br/>
 
Вывод строки <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>S\to(S)\to(SS)\to((S)S)\to((S)(S))\to(()(S))\to(()())</tex>.
  
 
Вывод строки <tex>((()())(()))</tex>:<br/>
 
Вывод строки <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>S\to(S)\to(SS)\rightarrow((S)S)\rightarrow((S)(S))\rightarrow</tex><br/>
 +
<tex>\rightarrow((SS)((S)))\rightarrow (((S)S)((S))) \rightarrow ((()S)((S)))\rightarrow</tex><br/><tex>\rightarrow((()(S))((S)))\rightarrow ((()())((S)))\rightarrow ((()())(()))</tex>.
  
 
===Арифметические выражения===
 
===Арифметические выражения===
<tex>\Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, *, /, -, (, )\}</tex>
+
<tex>\Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, *, /, -, (, )\}</tex>
 
<br/>
 
<br/>
  
Строка 75: Строка 72:
 
</tex><br/>
 
</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>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 \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>S \Rightarrow SOS \Rightarrow 2OS \Rightarrow 2+S \Rightarrow 2+SOS \Rightarrow 2+2OS \Rightarrow  2+2*S \Rightarrow  2+2*2</tex>.
  
 
===Язык <tex>0^n1^n2^n</tex>===
 
===Язык <tex>0^n1^n2^n</tex>===
  
Данный язык является [[Иерархия Хомского формальных грамматик#Класс 1 |контекстно-зависимым]]. КЗ-грамматика для языка приведена ниже, а через [[Лемма о разрастании для КС-грамматик#Пример доказательства неконтекстно-свободности языка с использованием леммы | лемму о разрастании]] доказывается его неконтекстно-свободность.  
+
Данный язык является [[Иерархия Хомского формальных грамматик#Класс 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 0$TS$2 \\
T0 \rightarrow 0T \\  
+
$T$0 \rightarrow 0$T$ \\  
T1 \rightarrow 11  
+
$T$1 \rightarrow 11  
 
</tex>
 
</tex>
  
 
Вывод строки <tex>000111222</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>
+
$S $ \Rightarrow 0$TS$2 \Rightarrow 0$T0TS$22 \Rightarrow 0$T0T$01222 \Rightarrow  0$T00T1$222 \Rightarrow \\
Данная грамматика описывает этот язык, так как мы можем вывести любую строку одним методом. <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> раз последнее правило и в результате получаем искомую строку.
+
\Rightarrow 00$T0T$1222 \Rightarrow 000$TT$1222 \Rightarrow 000$T$11222 \Rightarrow 000111222.
 +
</tex>
  
 
== См. также ==
 
== См. также ==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: