В информатике , в частности в теории автоматов , двусторонний конечный автомат - это конечный автомат, которому разрешено перечитывать свой ввод.
Двусторонний детерминированный конечный автомат
Двусторонний детерминированный конечный автомат ( 2DFA ) является абстрактной машины , обобщенный вариант детерминированного конечного автомата (DFA) , который может пересмотреть символы уже обработаны. Как и в DFA, существует конечное количество состояний с переходами между ними на основе текущего символа, но каждый переход также помечен значением, указывающим, будет ли машина перемещать свою позицию на входе влево, вправо или оставаться в той же позиции. Эквивалентно, 2DFA можно рассматривать как машины Тьюринга только для чтения без рабочей ленты, только входную ленту только для чтения.
2DFAs были введены в семенных 1959 бумаге Рабина и Скотт , [1] , который доказал , что они имеют эквивалентную мощность в одну сторону ДКА . То есть любой формальный язык, который может быть распознан с помощью 2DFA, может быть распознан с помощью DFA, который только исследует и использует каждый символ по порядку. Поскольку DFA, очевидно, являются частным случаем 2DFA, это означает, что оба типа машин распознают именно класс регулярных языков . Однако эквивалентный DFA для 2DFA может потребовать экспоненциально много состояний, что делает 2DFA гораздо более практичным представлением алгоритмов для некоторых общих проблем.
2DFA также эквивалентны машинам Тьюринга, доступным только для чтения, которые используют только постоянное количество места на своей рабочей ленте, поскольку любой постоянный объем информации может быть включен в состояние конечного управления через конструкцию продукта (состояние для каждой комбинации рабочей ленты). состояние и состояние контроля).
Формальное описание
Формально двусторонний детерминированный конечный автомат можно описать следующей восьмеркой : где
- конечный непустой набор состояний
- конечный непустой набор входного алфавита
- левый крайний маркер
- это правый конечный маркер
- это начальное состояние
- это конечное состояние
- это состояние отказа
Кроме того, должны быть выполнены следующие два условия:
- Для всех
- для некоторых
- для некоторых
Он говорит, что должен быть возможен какой-то переход, когда указатель на алфавите достигает конца.
- Для всех символов
В нем говорится, что как только автомат достигает состояния принятия или отклонения, он остается там навсегда, а указатель переходит на крайний правый символ и бесконечно циклически перемещается там. [2]
Двусторонний недетерминированный конечный автомат
Двухсторонняя недетерминирован конечный автомат (2NFA) может иметь несколько переходов , определенные в одной и той же конфигурации. Его переходная функция
- .
Как и стандартный односторонний NFA , 2NFA принимает строку, если принимает хотя бы одно из возможных вычислений. Как и 2DFA, 2NFA также принимают только обычные языки.
Двусторонний знакопеременный конечный автомат
Двухсторонний переменные конечный автомат (2AFA) является двусторонний расширением из переменных конечного автомата (AFA). Его набор состояний
- где .
Государства в а также называются экзистенциальными соотв. универсальный . В экзистенциальном состоянии 2AFA недетерминированно выбирает следующее состояние, как NFA, и принимает его, если принимает хотя бы одно из результирующих вычислений. В универсальном состоянии 2AFA переходит ко всем следующим состояниям и принимает, если все результаты вычислений принимаются.
Компромиссы сложности состояния
Двусторонние и односторонние конечные автоматы, детерминированные, недетерминированные и чередующиеся, принимают один и тот же класс регулярных языков. Однако преобразование автомата одного типа в эквивалентный автомат другого типа приводит к резкому увеличению числа состояний. Капуцис [3] определил, что преобразование-state 2DFA для эквивалентного DFA требует состояния в худшем случае. Если-состояние 2DFA или 2NFA преобразуется в NFA, наихудшее количество требуемых состояний равно . Ладнер , Липтон и Штокмейер . [4] доказали, что-состояние 2AFA может быть преобразовано в DFA с помощью состояния. Для преобразования 2AFA в NFA требуетсясостояний в худшем случае, см. Гефферт и Охотин. [5]
Каждый -состояние 2NFA имеет эквивалент -состояние 2DFA?
Это открытый вопрос, можно ли преобразовать каждую 2NFA в 2DFA только с полиномиальным увеличением количества состояний. Проблема была поднята Sakoda и Sipser , [6] , который сравнил его с P против NP задачи в теории сложности вычислений . Берман и Лингас [7] обнаружили формальную связь между этой проблемой и открытой проблемой L vs. NL , точную связь см. Капуцис [8] .
Подметальные автоматы
Подметающие автоматы - это 2DFA особого типа, которые обрабатывают входную строку, выполняя чередующиеся развертки слева направо и справа налево, поворачиваясь только на концевых маркерах. Сипсер [9] построил последовательность языков, каждый из которых принимается NFA с n состояниями, но не принимается никакими быстрыми автоматами с меньшим, чем состояния.
Двусторонний квантовый конечный автомат
Концепция 2DFAs в 1997 году обобщается на квантовые вычислениях с помощью Джона Уотраус «s„О мощности 2-Way Quantum конечного автомата“, в котором он демонстрирует , что эти машины могут распознавать нерегулярные языки и поэтому являются более мощным , чем ДКА. [10]
Двусторонний выталкивающий автомат
Магазинный автомат , который может перемещаться в любую сторону на его входной ленте называется двухсторонняя магазинный автомат ( 2PDA ); [11] он был изучен Хартманисом, Льюисом и Стернсом (1965). [12] Ахо, Хопкрофт, Ульман (1968) [13] и Кук (1971) [14] охарактеризовали класс языков, распознаваемых с помощью детерминированных ( 2DPDA ) и недетерминированных ( 2NPDA ) двусторонних автоматов выталкивания; Грей, Харрисон и Ибарра (1967) исследовали закрывающие свойства этих языков. [15]
Рекомендации
- ^ Рабин, Майкл O .; Скотт, Дана (1959). «Конечные автоматы и проблемы их решения». Журнал исследований и разработок IBM . 3 (2): 114–125. DOI : 10.1147 / rd.32.0114 .
- ^ Это определение было взято из лекций CS682 (Теория вычислений) Декстера Козена из Стэнфордского университета.
- ^ Капуцис, Христос (2005). «Удаление двунаправленности из недетерминированных конечных автоматов». В J. Jedrzejowicz, A.Szepietowski (ed.). Математические основы информатики . MFCS 2005. 3618 . Springer. С. 544–555. DOI : 10.1007 / 11549345_47 .
- ^ Ladner, Ричард Э .; Липтон, Ричард Дж .; Стокмейер, Ларри Дж. (1984). «Чередование автоматов выталкивания и стека». SIAM Journal on Computing . 13 (1): 135–155. DOI : 10.1137 / 0213010 . ISSN 0097-5397 .
- ^ Гефферт, Вильям; Охотин, Александр (2014). «Преобразование двусторонних чередующихся конечных автоматов в односторонние недетерминированные автоматы». Математические основы информатики 2014 . Конспект лекций по информатике. 8634 . С. 291–302. DOI : 10.1007 / 978-3-662-44522-8_25 . ISBN 978-3-662-44521-1. ISSN 0302-9743 .
- ^ Сакода, Уильям Дж .; Сипсер, Майкл (1978). Недетерминизм и размер двусторонних конечных автоматов . STOC 1978. ACM. С. 275–286. DOI : 10.1145 / 800133.804357 .
- ^ Берман, Петр; Лингас, Анджей (1977). О сложности регулярных языков в терминах конечных автоматов . Отчет 304. Польская академия наук.
- ^ Капуцис, Христос А. (2014). «Двусторонние автоматы против логарифмического пространства». Теория вычислительных систем . 55 (2): 421–447. DOI : 10.1007 / s00224-013-9465-0 .
- ^ Сипсер, Майкл (1980). "Нижние границы размеров подметающих автоматов". Журнал компьютерных и системных наук . 21 (2): 195–202. DOI : 10.1016 / 0022-0000 (80) 90034-3 .
- ^ Джон Уотроус . О мощности двусторонних квантовых конечных автоматов . CS-TR-1997-1350. 1997. pdf
- ^ Джон Э. Хопкрофт; Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Эддисон-Уэсли. ISBN 978-0-201-02988-8.Здесь: с.124; этот абзац опущен в издании 2003 года.
- ^ Дж. Хартманис; П. М. Льюис II, Р. Э. Стернс (1965). «Иерархии вычислений с ограниченной памятью». Proc. 6-я Энн. IEEE Symp. по теории коммутационных цепей и логическому проектированию . С. 179–190.
- ^ Альфред В. Ахо; Джон Э. Хопкрофт; Джеффри Д. Ульман (1968). "Время и ленточная сложность языков автоматов с расширением" . Информация и контроль . 13 (3): 186–206. DOI : 10.1016 / s0019-9958 (68) 91087-5 .
- ^ С. А. Кук (1971). «Линейное моделирование детерминированных двухсторонних автоматов с опусканием во времени». Proc. Конгресс ИФИП . Северная Голландия. С. 75–80.
- ^ Джим Грей; Майкл А. Харрисон; Оскар Х. Ибарра (1967). «Двусторонние автоматические выталкивающие машины» . Информация и контроль . 11 (1–2): 30–70. DOI : 10.1016 / s0019-9958 (67) 90369-5 .