Изменения

Класс 1 Первый класс представлен '''неукорачивающими грамматиками.'''и '''контекстно-зависимыми''' грамматиками.

'''Неукорачивающие грамматики''' - это [[те формальные грамматики]], всякое правило из <tex>P</tex> которых имеет вид <tex>\alpha\rightarrow\beta</tex>, где <tex>\alpha , \beta \in \{\Sigma\cup N\}^{+}</tex> и <tex>|\alpha|\leq|\beta|</tex>(возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил.}} {{Определение|definition ='''Контекстно-зависимые грамматики''' - это те формальные грамматики, всякое правило из <tex>P</tex> которых имеет вид <tex>\alpha A \beta\rightarrow\alpha\gamma\beta</tex>, где <tex>\alpha , \beta \in \{\Sigma\cup N\}^{+*}</tex> и <tex>|\alpha|gamma \in \{\Sigma\leq|cup N\beta|}^{+}</tex>, кроме, (возможно, правило <tex>$S$ \rightarrow to \epsilonvarepsilon</tex>. Однако, если такое правило существует, но тогда <tex>$S$</tex> не встречается в правых частях остальных правил).}} Как будет показано [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|далее]] неукорачивающие грамматики эквивалентны контекстно зависимым.