Войти
В информатике, линейный ограниченный автомат (множественное число линейные ограниченные автоматы, сокращенно LBA ) является ограниченная форма машины Тьюринга.
Линейный ограниченный автомат - это недетерминированная машина Тьюринга, которая удовлетворяет следующим трем условиям:
Другими словами: вместо потенциально бесконечной ленты для вычислений вычисление ограничивается частью ленты, содержащей ввод, плюс два квадрата ленты, удерживающие маркеры концов.
Альтернативное, менее ограничительное определение выглядит следующим образом:
Это ограничение делает LBA несколько более точной моделью реального компьютера, чем машина Тьюринга, определение которой предполагает неограниченное количество лент.
Сильное и более слабое определение приводят к одинаковым вычислительным возможностям соответствующих классов автоматов из-за теоремы о линейном ускорении.
Линейный ограниченный автоматы являются акцепторами для класса контекстно-зависимых языков. Единственное ограничение, наложенное на грамматики для таких языков, - это то, что никакое производство не отображает строку в более короткую строку. Таким образом, ни один вывод строки на контекстно-зависимом языке не может содержать текстовую форму длиннее самой строки. Поскольку существует взаимно однозначное соответствие между автоматами с линейными ограничениями и такими грамматиками, для распознавания этой строки автоматом не требуется больше ленты, чем занято исходной строкой.
В 1960 году Джон Майхилл представил модель автомата, известную сегодня как детерминированный линейный ограниченный автомат. В 1963 году Питер С. Ландвебер доказал, что языки, принятые детерминированными LBA, контекстно-зависимы. В 1964 г. С.-Ю. Курода представил более общую модель (недетерминированных) линейных ограниченных автоматов, отметил, что доказательство Ландвебера также работает для недетерминированных линейных ограниченных автоматов, и показал, что принятые ими языки являются именно контекстно-зависимыми языками.
В своей основополагающей статье Курода также изложил две исследовательские задачи, которые впоследствии стали известны как «проблемы LBA»: первая проблема LBA заключается в том, равен ли класс языков, принятых LBA, класс языков, принятый детерминированной LBA. Эту проблему можно кратко сформулировать на языке теории сложности вычислений как:
Вторая проблема LBA заключается в том, закрыт ли класс языков, принимаемых LBA, при дополнении.
Как уже отмечал Курода, отрицательный ответ на вторую проблему LBA будет означать отрицательный ответ на первую задачу. Но у второй проблемы LBA есть утвердительный ответ, что следует из теоремы Иммермана – Селепсеньи, доказанной через 20 лет после того, как проблема была поднята. На сегодняшний день первая проблема LBA остается открытой. Теорема Сэвича дает начальное представление о том, что NSPACE (O (n)) ⊆ DSPACE(O(n)).
