stringtranslate.com

Линейный ограниченный автомат

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

Операция

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

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

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

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

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

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

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

История

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

Проблемы с 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 лет после того, как проблема была поднята. [6] [7] На сегодняшний день первая проблема LBA все еще остается открытой. Теорема Сэвича дает начальное представление о том, что NSPACE (O( n )) ⊆ DSPACE (O( n 2 )). [8]

Ссылки

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

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