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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 7: Строка 7:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
   '''Язык грамматики''' - множество <tex>L(\Gamma) = \{\omega|S \Rightarrow^{*}\omega, \omega \in \Sigma^{*}\} </tex>
+
   '''Язык грамматики''' - множество <tex>L(\Gamma) = \{\omega|S \Rightarrow^{*}\omega, \omega \in \Sigma^{*}\}</tex>, где <tex>\Rightarrow^{*} </tex> обозначает, что слово <tex>\omega</tex> выводимо из нетерминала <tex>S</tex> за некоторое число шагов.
 
}}
 
}}
 
То есть, <tex>L(\Gamma)</tex> - это все цепочки в алфавите <tex>\Sigma</tex>, которые выводимы из <tex>S</tex> с помощью <tex>P</tex>.
 
То есть, <tex>L(\Gamma)</tex> - это все цепочки в алфавите <tex>\Sigma</tex>, которые выводимы из <tex>S</tex> с помощью <tex>P</tex>.

Версия 01:01, 29 октября 2010

Определение:
Формальная грамматика - четверка
 [math]\Gamma =\langle \Sigma, N, S \in N, P \in 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]L(\Gamma) = \{\omega|S \Rightarrow^{*}\omega, \omega \in \Sigma^{*}\}[/math], где [math]\Rightarrow^{*} [/math] обозначает, что слово [math]\omega[/math] выводимо из нетерминала [math]S[/math] за некоторое число шагов.

То есть, [math]L(\Gamma)[/math] - это все цепочки в алфавите [math]\Sigma[/math], которые выводимы из [math]S[/math] с помощью [math]P[/math].