Изменения
Нет описания правки
Языки, заданные этими грамматиками, распознаются с помощью '''линейно ограниченного автомата''' (англ. ''linear bounded automaton'') (недетерминированная машина Тьюринга, чья лента ограничена константой, зависящей от длины входа.)
Как будет показано [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|далеев другом конспекте]], неукорачивающие грамматики эквивалентны контекстно-зависимым.
===Пример===
Терминалы: буквы алфавита <tex>\Sigma</tex>
Нетерминалы: <tex>N = \{S\}</tex>
Продукции: <tex>S\rightarrow\alpha S\alpha\,|\,\alpha\,|\,\varepsilon, \alpha \in \Sigma</tex>;
Оба вида задают одинаковые языки. При этом если правила леволинейной и праволинейной грамматик объединить, то язык будет уже не обязан быть регулярным.
===Пример===
