2.4. Линейно ограниченные автоматы и языки типа 1

Линейно ограниченным автоматом (-автоматом) называют машину Тьюринга, которой запрещено передвигать читающую головку за пределы участка входной ленты, занятого входной

почкой. Это можно достичь, добавив к входному языку два специальных символа (обычно ). Их помещают в начале и в конце входной цепочки, которая после этого превращается в Правила перехода ЛO-автомата подобны правилам для МТ за исключением того, что если прочитан символ или то читающая головка передвигается на одну ячейку вправо или влево.

Линейно ограниченный автомат представляет собой модель программы с неограниченным доступом к конечной области «динамического» участка памяти, причем размер этой области можно определить, исследуя входную цепочку в ходе работы программы перед анализом приемлемости входной цепочки. Фактически можно просто считать, что какая-то часть ленты требуется для ввода как стираемая зона.

Модель ЛО-автомата имеет неочевидное приложение в программировании. Напомним, что автомат называется детерминированным, если для каждого сочетания сигнала на входе и внутреннего состояния существует не более одного правила перехода, определяющего его следующее действие. Автомат называется недетерминированным, если данная комбинация вход — внутреннее состояние служит левой частью более чем одного правила перехода. Когда речь шла о машине Тьюринга, разница между детерминированными и недетерминированными автоматами не рассматривалась, поскольку можно показать, что для каждой недетерминированной машины Тьюринга существует эквивалентная ей детерминированная. Для ЛО-автоматов не известно, так это или нет, поэтому, пока ответ не получен, благоразумный программист должен считать, что если ему нужно написать программу, моделью которой является ЛО-автомат, то он должен считать этот автомат недетерминированным. Для недетерминированного автомата может возникнуть возможность выбора конкретного правила перехода при предъявлении определенной конфигурации памяти. Если выбор сделан неверно, то автомат может впоследствии прийти в состояние останова, не приняв цепочки. В этом случае надо вернуться к моменту выбора и попытаться принять цепочку, избирая другой путь вычислений. Это можно сделать только в том случае, когда сохраняются весьма точные записи предыдущих действий.

Теоретический результат в области ЛО-автоматов таков:

Язык воспринимается ЛО-автоматом тогда и только тогда, когда это язык типа 1.

Этот результат не находит широких приложений, поскольку, как мы показали, ЛО-автоматы моделируют сложные программы. В то же время доказательство того, что областью определения функции является контекстно-зависимый язык, может оказаться полезным, так как оно выявляет возможности управления памятью и

хранения записей, необходимые программе для вычисления Чаще используется другой результат.

Все контекстно-зависимые языки рекурсивны.

Здесь утверждается, что если областью определения функции является язык типа 1, то можно написать программу (возможно, сложную), которая с гарантией воспринимает все цепочки и дает либо значение либо надежное указание на то, что для функция не определена.

Рис. 2.8. Работа МП-автомата. Сначала машина находится в состоянии и читает символ на входе и символ в магазине. При первом переходе входная лента движется вперед и заталкивается в магазив. Машина оказывается в состоянии На втором шаге входная лента движется, читая считывается и выталкивается из магазина, а машина переходит в состояние

С другой стороны, неудачная попытка доказать, что — язык типа 1 или даже типа 0, не гарантирует, что язык не рекурсивен. Существуют рекурсивные языки, которые не могут порождаться грамматикой типа 1.