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