Изменения

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

К нулевому классу Хомского относятся все [[Формальные_грамматики|формальные грамматики ]]. Элементы этого класса называются '''неограниченными грамматиками''' (англ. ''unrestricted grammars''), поскольку на них не накладывается никаких ограничений. Они задают все языки, которые могут быть распознаны [[Машина_Тьюринга|машиной Тьюринга]]. Эти языки также известны как '''[[Перечислимые_языки|рекурсивно перечислимые]]''' (англ. ''recursively enumerable'').  Правила можно записать в виде: <tex> \Gamma = alpha \langlerightarrow \Sigmabeta</tex>, Nгде <tex>\alpha</tex> — любая непустая цепочка, содержащая хотя бы один нетерминальный символ, а <tex>\beta</tex> — любая цепочка символов из алфавита. Практического применения в силу своей сложности такие грамматики не имеют. ===Пример===Продукции: <tex>S \rightarrow aBcc \\B \rightarrow A \\BAA \rightarrow d \\Ac \rightarrow B \\A \rightarrow AAA\ |\ dB \\</tex> Выведем в данной грамматике строку <tex>addd</tex>: <tex>\boldsymbol{S } \in N,PRightarrow a\boldsymbol{B}cc \Rightarrow a\boldsymbol{Ac}c \Rightarrow a\boldsymbol{B}c \Rightarrow a\boldsymbol{Ac} \Rightarrow a\boldsymbol{B} \Rightarrow a\boldsymbol{A} \Rightarrow ad\boldsymbol{B} \Rightarrow ad\subset N^boldsymbol{*A}\times (Rightarrow ad\boldsymbol{A}AA \SigmaRightarrow add\cup N)^boldsymbol{*BAA}\rangleRightarrow addd</tex>, на которые не накладывается никаких ограничений, кроме указанных в определении понятия [[формальные грамматики]].

Класс 1 Первый класс представлен '''неукорачивающими ''' и '''контекстно-зависимыми''' грамматиками.{{Определение|id = Неукорачивающие грамматики|definition ='''Неукорачивающая грамматика''' (англ. ''noncontracting grammar'') {{---}} это формальная грамматика, всякое правило из <tex>P</tex> которой имеет вид <tex>\alpha\rightarrow\beta</tex>, где <tex>\alpha , \beta \in \{\Sigma\cup N\}^{+}</tex> и <tex>|\alpha| \leqslant |\beta|</tex> (возможно правило <tex>S \rightarrow \varepsilon</tex>, но тогда <tex>S</tex> не встречается в правых частях правил).}}

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

Класс 2 Второй класс составляют [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободные грамматики]], которые задают контекстно-свободные языки. Эти языки распознаются с помощью [[Автоматы_с_магазинной_памятью|автоматов с магазинной памятью]].

'''Контекстно-свободные грамматики свободная грамматика''' (англ. ''context- free grammar'') {{---}} это [[формальные грамматики]]формальная грамматика, всякое правило из <tex>P</tex> которых которой имеет вид <tex>A \rightarrow\beta</tex>, где <tex>A\in N </tex>, <tex>\beta \in \{\Sigma \cup N\}^{+}</tex>.

Класс 3 составляют К третьему типу относятся '''автоматные''' или '''регулярные грамматики''' (англ. ''regular grammars'') {{---}} самые простые из формальных грамматик, которые задают [[праволинейные(автоматные) грамматикиРегулярные_языки:_два_определения_и_их_эквивалентность|регулярные языки]].Они являются контекстно-свободными, но с ограниченными возможностями. Все регулярные грамматики могут быть разделены на два эквивалентных класса следующего вида:

Праволинейные'''Леволинейная грамматика''' (автоматныеангл. ''left-regular grammar'') грамматики {{--- }} это [[формальные грамматики]]формальная грамматика, всякое правило из <tex>P</tex> которых которой имеет вид <tex>A \rightarrow tBB\gamma</tex> либо или <tex>A \rightarrow t\gamma</tex>, где <tex>A\gamma \in N</tex>\Sigma, A,<tex>B\in N</tex>, <tex>t\in \Sigma </tex>.