Изменения

'''Иерархия Хомского ''' — классификация [[формальных языков]] и [[формальных грамматик]], согласно которой они делятся на 4 класса по их условной сложности.

''' == Класс 0'''.== К нулевому классу Хомского относятся грамматики <tex> \Gamma = <\langle\Sigma, N, S \in N,P\subset N^{*}\times (\Sigma\cup N)^{*}>\rangle</tex>, на которые не накладывается никаких ограничений, кроме указанных в определении понятия [[формальные грамматики]].

''' == Класс 1'''.== Класс 1 представлен '''неукорачивающими грамматиками.'''

'''Неукорачивающие грамматики ''' - это [[формальные грамматики]], всякое правило из <tex>P</tex> которых имеет вид <tex>\alpha\rightarrow\beta</tex>, где <tex>\alpha \in \{\Sigma\bigcup cup N\}^{+}</tex>, <tex>\beta \in \{\Sigma\bigcup cup N\}^{+}</tex> и <tex>|\alpha|\leq|\beta|</tex>, кроме, возможно, <tex>S\rightarrow \epsilon</tex>. Однако, если такое правило существует, <tex>S</tex> не встречается в правых частях остальных правил.

''' == Класс 2'''.== Класс 2 составляют [[контекстно-свободные грамматики]].

всякое правило из <tex>P</tex> которых имеет вид <tex>A \rightarrow\beta</tex>, где <tex>A\in N </tex>, <tex>\beta \in \{\Sigma \bigcup cup N\}^{+}</tex>.

''' == Класс 3'''.== Класс 3 составляют [[праволинейные(автоматные) грамматики]].