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

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

Операция

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

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

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

Альтернативное, менее ограничительное определение выглядит следующим образом:

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

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

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

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

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

История

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

LBA проблемы

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

Первая проблема LBA : NSPACE (O (n)) = DSPACE (O (n))?

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

Вторая проблема LBA : NSPACE (O (n)) = co- NSPACE (O (n))?

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

Ссылки

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

внешние ссылки