Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В информатике , в линейном ограниченном автомате ( во множественном числе линейного ограниченных автоматов , сокращенно 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 (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. ^ a b c d Джон Э. Хопкрофт ; Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Эддисон-Уэсли. ISBN 978-0-201-02988-8. CS1 maint: обескураженный параметр ( ссылка )
  2. ^ Джон Myhill (июнь 1960). Линейно ограниченные автоматы (Техническое примечание WADD). Авиационная база Райт-Паттерсона, отдел развития воздуха Райт, Огайо. CS1 maint: обескураженный параметр ( ссылка )
  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 . CS1 maint: обескураженный параметр ( ссылка )
  5. ^ Willem JM левелевский (2008). Введение в теорию формальных языков и автоматов . Издательство Джона Бенджамина. С. 126–127. ISBN 978-90-272-3250-2. CS1 maint: обескураженный параметр ( ссылка )
  6. ^ Иммерман, Нил (1988), "Недетерминированные пространство закрыто под дополнительности" (PDF) , SIAM журнал по вычислениям , 17 (5): 935-938, DOI : 10,1137 / 0217058 , MR 0961049   CS1 maint: обескураженный параметр ( ссылка )
  7. ^ Szelepcsényi, Роберт (1988), "Метод принуждения для недетерминированных автоматов", Acta Informatica , 26 (3): 279–284
  8. ^ Арора, Санджив; Варак, Вооз (2009). Теория сложности: современный подход . Издательство Кембриджского университета. ISBN 978-0-521-42426-4.

Внешние ссылки [ править ]

  • Линейная Bounded Automata по Forbes Д. Льюис
  • Слайды «Линейно ограниченные автоматы» , часть « Контекстно-зависимых языков » Артура К. Флека
  • Линейно-ограниченные автоматы , часть учебной программы по теории вычислений, Дэвид Матушек