Изменения

== Класс 1 ==

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

{{Определение

|id = Неукорачивающие грамматики

'''Неукорачивающая грамматика''' (англ. ''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> не встречается в правых частях правил).

}}

{{Определение

|definition =

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

}}

Языки, заданные этими грамматиками, распознаются с помощью '''линейно ограниченного автомата''' (англ. ''linear bounded automaton'') (недетерминированная машина Тьюринга, чья лента ограничена константой, зависящей от длины входа.)

== Класс 2 ==

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

{{Определение

|definition =

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

}}

То есть грамматика допускает появление в левой части правила только нетерминального символа.

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

}}

{{Определение

|definition =

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

}}

Оба вида задают одинаковые языки. При этом если правила леволинейной и праволинейной грамматик объединить, то язык будет уже не обязан быть регулярным.

* [[Разрешимые_(рекурсивные)_языки|Разрешимые (рекурсивные) языки]]

* [[Возможность_порождения_формальной_грамматикой_произвольного_перечислимого_языка|Возможность порождения формальной грамматикой произвольного перечислимого языка]]

==Источники информации==