Методы искусственного интеллекта для машинного перевода текстов. Роганов В.Р - 28 стр.

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



                                                                           28