14
правок
Изменения
м
Нет описания правки
== Класс 0 ==
К нулевому классу Хомского относятся грамматики <tex> \Gamma = \langle\Sigma, N, S \in N,P\subset N^{*}\times (\Sigma\cup N)^{*}\rangle</tex>, на которые не накладывается никаких ограничений, кроме указанных в определении понятия [[формальные грамматики]].
== Класс 1 ==
Класс 1 представлен '''неукорачивающими грамматиками.'''
|definition =
'''Неукорачивающие грамматики''' - это [[формальные грамматики]],
всякое правило из <tex>P</tex> которых имеет вид <tex>\alpha\rightarrow\beta</tex>, где <tex>\alpha \in \{\Sigma\cup N\}^{+}</tex>, <tex>\beta \in \{\Sigma\cup N\}^{+}</tex> и <tex>|\alpha|\leq|\beta|</tex>, кроме, возможно, <tex>S\rightarrow \epsilon</tex>. Однако, если такое правило существует, <tex>S</tex> не встречается в правых частях остальных правил. }}
== Класс 2 ==
Класс 2 составляют [[контекстно-свободные грамматики]].
{{Определение
|definition =
'''Контекстно-свободные грамматики ''' - это [[формальные грамматики]], всякое правило из <tex>P</tex> которых имеет вид <tex>A \rightarrow\beta</tex>, где <tex>A\in N </tex>, <tex>\beta \in \{\Sigma \cup N\}^{+}</tex>.}}
== Класс 3 ==
Класс 3 составляют [[праволинейные(автоматные) грамматики]].
{{Определение
|definition =
'''Праволинейные(автоматные) грамматики ''' - это [[формальные грамматики]], всякое правило из <tex>P</tex> которых имеет вид <tex>A \rightarrow tB</tex> либо <tex>A \rightarrow t</tex>, где <tex>A\in N</tex>,<tex>B\in N</tex>, <tex>t\in \Sigma </tex>.}}
