Формальные грамматики

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Формальная грамматика - четверка
 [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]L(\Gamma)[/math] - это все цепочки в алфавите [math]\Sigma[/math], которые выводимы из [math]S[/math] с помощью [math]P[/math].