Изменения
Нет описания правки
{{Определение
|definition = '''Линейно ограниченный автомат''' ''(lba)'' — недетерминированная одноленточная [[Машина Тьюринга|машина Тьюринга]], которая никогда не покидает те ячейки, на которых размещен ее ввод.}}
Более формально:
{{Теорема
|statement=
Если <tex>L</tex> — [[Иерархия Хомского формальных грамматик#Класс 1|контекстно-зависимый язык]], то язык <tex>L</tex> принимается некоторым линейно ограниченным автоматом.
|proof=
Пусть <tex>G = \langle V_N , V_T, P, S\rangle</tex> — контекстно-зависимая грамматика. Мы построим lba <tex>M</tex>, такой, что язык, принимаемый lba <tex>M</tex>, есть <tex>L(G)</tex>.
== См. также ==
* [[Машина Тьюринга]]
* [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбораИерархия Хомского формальных грамматик#Класс 1|Контекстно-свободные зависимые грамматики]]
== Литература ==
* Мартыненко Б.К. Языки и трансляции: Учеб. пособие ISBN 5-288-02870-2
