Линейный ограниченный автомат - Linear bounded automaton

В Информатика, а линейно ограниченный автомат (множественное число линейно ограниченные автоматы, сокращенно LBA) является ограниченной формой Машина Тьюринга.

Операция

Линейный ограниченный автомат - это недетерминированная машина Тьюринга который удовлетворяет следующим трем условиям:

  • Его входной алфавит включает два специальных символа, служащих левым и правым маркерами конца.
  • Его переходы не могут печатать другие символы поверх конечных маркеров.
  • Его переходы не могут перемещаться ни слева от левого маркера конца, ни справа от правого маркера конца.[1]:225

Другими словами: вместо того, чтобы иметь потенциально бесконечную ленту для вычислений, вычисления ограничиваются той частью ленты, которая содержит ввод, плюс два квадрата ленты, удерживающие маркеры концов.

Альтернатива, менее ограничительное определение как следует:

  • Как Машина Тьюринга, LBA имеет ленту, состоящую из ячеек, которые могут содержать символы из конечный алфавит, головка, которая может читать или записывать в одну ячейку на ленте за раз и может перемещаться, и конечное число состояний.
  • LBA отличается от Машина Тьюринга в том, что, хотя изначально считается, что лента имеет неограниченную длину, только конечная прилегающая часть ленты, длина которой равна линейная функция длины начального ввода, к которому может получить доступ головка чтения / записи; отсюда и название линейно ограниченный автомат.[1]:225

Это ограничение делает LBA несколько более точной моделью реального мира. компьютер чем машина Тьюринга, определение которой предполагает неограниченную ленту.

Сильное и более слабое определение приводят к одинаковым вычислительным возможностям соответствующих классов автоматов,[1]:225 из-за теорема о линейном ускорении.

LBA и контекстно-зависимые языки

Линейно ограниченные автоматы акцепторы для класса контекстно-зависимые языки.[1]:225–226 Единственное ограничение на грамматики для таких языков не существует производства, отображающего строку в более короткую строку. Таким образом, вывод строки на контекстно-зависимом языке не может содержать сентенциальная форма длиннее самой струны. Поскольку существует взаимно однозначное соответствие между автоматами с линейными ограничениями и такими грамматиками, для распознавания этой строки автоматом не требуется больше ленты, чем та, которая занята исходной строкой.

История

В 1960 г. Джон Майхилл представил модель автомата, известную сегодня как детерминированный линейный ограниченный автомат.[2] В 1963 г. Питер Ландвебер доказал, что языки, принятые детерминированными LBA, контекстно-зависимы.[3] В 1964 г. С.-Ю. Курода представил более общую модель (недетерминированных) линейных ограниченных автоматов, отметил, что доказательство Ландвебера также работает для недетерминированных линейных ограниченных автоматов, и показал, что принятые ими языки являются в точности контекстно-зависимыми языками.[4][5]

LBA проблемы

В своей основополагающей статье Курода также сформулировал две исследовательские задачи, которые впоследствии стали известны как «проблемы LBA»: первая проблема LBA заключается в том, равен ли класс языков, принимаемых LBA, классу языков, принятых детерминированным LBA. Эту проблему можно кратко сформулировать на языке теория сложности вычислений в качестве:

Первая проблема LBA: Является NSPACE(О (п)) = DSPACE(На))?

Вторая проблема LBA заключается в том, является ли класс языков, принимаемых LBA, закрытым при дополнении.

Вторая проблема LBA: Является NSPACE(О (п)) = со-NSPACE(На))?

Как уже заметил Курода, отрицательный ответ на вторую проблему LBA будет означать отрицательный ответ на первую проблему. Но вторая проблема LBA имеет положительный ответ, что подразумевает Теорема Иммермана – Селепсеньи доказано через 20 лет после того, как проблема была поднята.[6][7] На сегодняшний день первая проблема LBA остается открытой. Теорема савича дает первоначальное представление о том, что NSPACE(O (n)) ⊆ DSPACE(На2)).[8]

Рекомендации

  1. ^ а б c d Джон Э. Хопкрофт; Джеффри Д. Уллман (1979). Введение в теорию автоматов, языки и вычисления. Эддисон-Уэсли. ISBN  978-0-201-02988-8.
  2. ^ Джон Майхилл (Июнь 1960 г.). Линейно ограниченные автоматы (Техническая записка WADD). Авиационная база Райт-Паттерсона, отдел развития воздуха Райт, Огайо.
  3. ^ P.S. Ландвебер (1963). "Три теоремы о грамматиках фразовой структуры типа 1". Информация и контроль. 6 (2): 131–136. Дои:10.1016 / с0019-9958 (63) 90169-4.
  4. ^ Сигэ-Юки Курода (Июнь 1964 г.). «Классы языков и линейно-ограниченные автоматы». Информация и контроль. 7 (2): 207–223. Дои:10.1016 / с0019-9958 (64) 90120-2.
  5. ^ Виллем Дж. М. Левелт (2008). Введение в теорию формальных языков и автоматов. Издательство Джона Бенджамина. С. 126–127. ISBN  978-90-272-3250-2.
  6. ^ Иммерман, Нил (1988), «Недетерминированное пространство закрыто при дополнении» (PDF), SIAM Журнал по вычислениям, 17 (5): 935–938, Дои:10.1137/0217058, МИСТЕР  0961049
  7. ^ Селепсеньи, Роберт (1988), «Метод принуждения для недетерминированных автоматов», Acta Informatica, 26 (3): 279–284
  8. ^ Арора, Санджив; Варак, Вооз (2009). Теория сложности: современный подход. Издательство Кембриджского университета. ISBN  978-0-521-42426-4.

внешняя ссылка