3622
правки
Изменения
м
→Класс 1
Языки, заданные этими грамматиками, распознаются с помощью '''линейно ограниченного автомата''' (англ. ''linear bounded automaton'') (недетерминированная машина Тьюринга, чья лента ограничена константой, зависящей от длины входа.)
[[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|Известно что]], что неукорачивающие грамматики эквивалентны контекстно-зависимым.
===Пример===
