Двусторонний конечный автомат

В информатике , в частности в теории автоматов , двусторонний конечный автомат — это конечный автомат , которому разрешено пересчитывать входные данные.

Двусторонний детерминированный конечный автомат

Двусторонний детерминированный конечный автомат ( 2DFA ) — это абстрактная машина , обобщенная версия детерминированного конечного автомата (DFA), которая может повторно обращаться к уже обработанным символам. Как и в DFA, существует конечное число состояний с переходами между ними в зависимости от текущего символа, но каждый переход также помечен значением, указывающим, будет ли машина перемещать свою позицию на входе влево, вправо или оставаться. на той же позиции. Аналогично, 2DFA можно рассматривать как машины Тьюринга только для чтения, без рабочей ленты, а только с входной лентой, доступной только для чтения.

2DFA были представлены в плодотворной статье Рабина и Скотта в 1959 году . ^[1] которые доказали, что их мощность эквивалентна односторонним DFA . То есть любой формальный язык , который может распознаваться 2DFA, может быть распознан DFA, который только проверяет и обрабатывает каждый символ по порядку. Поскольку DFA, очевидно, являются частным случаем 2DFA, это означает, что оба типа машин распознают именно класс регулярных языков . Однако эквивалентный DFA для 2DFA может потребовать экспоненциально большого количества состояний, что делает 2DFA гораздо более практичным представлением алгоритмов для некоторых распространенных проблем.

2DFA также эквивалентны машинам Тьюринга только для чтения , которые используют только постоянный объем пространства на своей рабочей ленте, поскольку любой постоянный объем информации может быть включен в состояние конечного управления через конструкцию продукта (состояние для каждой комбинации рабочих лент). состояние и состояние управления).

Формальное описание

Формально двусторонний детерминированный конечный автомат можно описать следующей восьмеркой : $M=(Q,\Sigma ,L,R,\delta ,s,t,r)$ где

$Q$ - конечное непустое множество состояний
$\Sigma$ - конечный непустой набор входных символов
$L$ это левый конечный маркер
$R$ это правильный конечный маркер
$\delta :Q\times (\Sigma \cup \{L,R\})\rightarrow Q\times \{\mathrm {left,right} \}$
$s$ это начальное состояние
$t$ это конечное состояние
$r$ это состояние отклонения

Кроме того, также должны быть соблюдены следующие два условия:

Для всех $q\in Q$

\delta (q,L)=(q^{\prime },\mathrm {right} )

для некоторых

q^{\prime }\in Q

\delta (q,R)=(q^{\prime },\mathrm {left} )

для некоторых

q^{\prime }\in Q

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

Для всех символов $\sigma \in \Sigma \cup \{L\}$ ^{[ нужны разъяснения ]}

\delta (t,\sigma )=(t,R)

\delta (r,\sigma )=(r,R)

\delta (t,R)=(t,L)

\delta (r,R)=(r,L)

В нем говорится, что как только автомат достигает состояния принятия или отклонения, он остается там навсегда, а указатель перемещается к самому правому символу и циклически перемещается там бесконечно. ^[2]

Двусторонний недетерминированный конечный автомат

Двусторонний недетерминированный конечный автомат (2NFA) может иметь несколько переходов, определенных в одной и той же конфигурации. Его переходная функция

$\delta :Q\times (\Sigma \cup \{L,R\})\rightarrow 2^{Q\times \{\mathrm {left,right} \}}$ .

Как и стандартный односторонний NFA , 2NFA принимает строку, если хотя бы одно из возможных вычислений принимает ее. Как и 2DFA, 2NFA также принимают только обычные языки.

Двусторонний попеременный конечный автомат

Двусторонний попеременный конечный автомат (2AFA) является двусторонним расширением попеременного конечного автомата (AFA). Его набор состояний

$Q=Q_{\exists }\cup Q_{\forall }$ где $Q_{\exists }\cap Q_{\forall }=\emptyset$ .

государства в $Q_{\exists }$ и $Q_{\forall }$ называются экзистенциальными соответственно. универсальный . В экзистенциальном состоянии 2AFA недетерминированно выбирает следующее состояние, как и NFA, и принимает его, если хотя бы одно из результирующих вычислений принимает его. В универсальном состоянии 2AFA переходит ко всем следующим состояниям и принимает, если все результирующие вычисления принимают.

Компромиссы сложности состояния

Двусторонние и односторонние конечные автоматы, детерминированные, недетерминированные и альтернирующие, принимают один и тот же класс регулярных языков. Однако преобразование автомата одного типа в эквивалентный автомат другого типа приводит к увеличению числа состояний. Христос Капуцис ^[3] установил, что преобразование $n$ -составить 2DFA для эквивалентного DFA $n(n^{n}-(n-1)^{n})$ государства в худшем случае. Если $n$ -state 2DFA или 2NFA преобразуется в NFA, требуемое количество состояний в худшем случае равно ${\binom {2n}{n+1}}=O\left({\frac {4^{n}}{\sqrt {n}}}\right)$ . Ладнер , Липтон и Стокмейер . ^[4] доказал, что $n$ -state 2AFA можно преобразовать в DFA с помощью $2^{n2^{n}}$ государства. Для преобразования 2AFA в NFA требуется $2^{\Theta (n\log n)}$ состояния в худшем случае см. Гефферт и Охотин. ^[5]

Нерешенная задача в информатике :

Каждый ли

n

-state 2NFA имеет эквивалент

\operatorname {poly} (n)

-состояние 2DFA?

(еще нерешенные проблемы по информатике)

Вопрос о том, можно ли преобразовать каждый 2NFA в 2DFA только с полиномиальным увеличением числа состояний, остается открытым. Проблему подняли Сакода и Сипсер . ^[6] который сравнил это с проблемой P против NP в теории сложности вычислений . Берман и Лингас ^[7] обнаружил формальную связь между этой проблемой и открытой проблемой L против NL , см. Капуцис. ^[8] для точного отношения.

Подметальные автоматы

Разверточные автоматы — это 2DFA особого типа, которые обрабатывают входную строку, выполняя попеременные проходы слева направо и справа налево, поворачиваясь только у конечных маркеров. Сипсер ^[9] построил последовательность языков, каждый из которых принимается NFA с n-состояниями, но не принимается ни одним очищающим автоматом с числом менее $2^{n}$ государства.

Двусторонний квантовый конечный автомат

Концепция 2DFA была в 1997 году обобщена на квантовые вычисления в книге Джона Уотруса «О силе двусторонних квантовых автоматов с конечными состояниями», в которой он демонстрирует, что эти машины могут распознавать нерегулярные языки и поэтому являются более мощными, чем DFA. ^[10]

Автомат двустороннего опускания

Автомат с выталкиванием , которому разрешено двигаться в любом направлении по входной ленте, называется автоматом с двусторонним выталкиванием ( 2PDA ); ^[11] его изучали Хартманис, Льюис и Стернс (1965). ^[12] Ахо, Хопкрофт, Ульман (1968) ^[13] и Кук (1971) ^[14] охарактеризовал класс языков, распознаваемых детерминированными ( 2DPDA ) и недетерминированными ( 2NPDA ) двусторонними автоматами; Грей, Харрисон и Ибарра (1967) исследовали свойства замыкания этих языков. ^[15]

Ссылки

^ Рабин, Майкл О.; Скотт, Дана (1959). «Конечные автоматы и проблемы их решения». Журнал исследований и разработок IBM . 3 (2): 114–125. дои : 10.1147/рд.32.0114 .
^ Это определение было взято из конспектов лекций CS682 (Теория вычислений) Декстера Козена из Стэнфордского университета.
^ Капуцис, Христос (2005). «Удаление двунаправленности из недетерминированных конечных автоматов». В Й. Енджейовиче, А. Шепетовском (ред.). Математические основы информатики . МФКС 2005. Том. 3618. Спрингер. стр. 544–555. дои : 10.1007/11549345_47 .
^ Ладнер, Ричард Э.; Липтон, Ричард Дж.; Стокмейер, Ларри Дж. (1984). «Попеременные автоматы с выталкиванием и стекированием». SIAM Journal по вычислительной технике . 13 (1): 135–155. дои : 10.1137/0213010 . ISSN 0097-5397 .
^ Гефферт, Вильям; Охотин, Александр (2014). «Преобразование двусторонних попеременных конечных автоматов в односторонние недетерминированные автоматы». Математические основы информатики 2014 . Конспекты лекций по информатике. Том. 8634. стр. 291–302. дои : 10.1007/978-3-662-44522-8_25 . ISBN 978-3-662-44521-1 . ISSN 0302-9743 .
^ Сакода, Уильям Дж.; Сипсер, Майкл (1978). Недетерминизм и размер двусторонних конечных автоматов . СТОК 1978. ACM. стр. 275–286. дои : 10.1145/800133.804357 .
^ Берман, Петр; Лингас, Анджей (1977). О сложности регулярных языков в терминах конечных автоматов . Том. Отчет 304. Польская академия наук.
^ Капуцис, Христос А. (2014). «Двусторонние автоматы против логарифмического пространства». Теория вычислительных систем . 55 (2): 421–447. дои : 10.1007/s00224-013-9465-0 .
^ Сипсер, Майкл (1980). «Нижние границы размера сметающих автоматов». Журнал компьютерных и системных наук . 21 (2): 195–202. дои : 10.1016/0022-0000(80)90034-3 .
^ Джон Уотрус . О мощности двусторонних квантовых автоматов с конечным состоянием . CS-TR-1997-1350. 1997. PDF
^ Джон Э. Хопкрофт; Джеффри Д. Уллман (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли. ISBN 978-0-201-02988-8 . Здесь: стр.124; этот абзац опущен в издании 2003 года.
^ Дж. Хартманис; Премьер-министр Льюис II, Р.Э. Стернс (1965). «Иерархии вычислений с ограниченной памятью». Учеб. 6-я Энн. Симптом IEEE. по теории коммутационных цепей и логическому проектированию . стр. 179–190.
^ Альфред В. Ахо; Джон Э. Хопкрофт; Джеффри Д. Уллман (1968). «Временная и ленточная сложность языков автоматов с pushdown» . Информация и контроль . 13 (3): 186–206. дои : 10.1016/s0019-9958(68)91087-5 .
^ С. А. Кук (1971). «Моделирование детерминированных двусторонних автоматов с линейным временем». Учеб. Конгресс ИФИП . Северная Голландия. стр. 75–80.
^ Джим Грей; Майкл А. Харрисон; Оскар Х. Ибарра (1967). «Автоматы с двусторонним нажатием». Информация и контроль . 11 (1–2): 30–70. дои : 10.1016/s0019-9958(67)90369-5 .

[1] Рабин, Майкл О.; Скотт, Дана (1959). «Конечные автоматы и проблемы их решения». Журнал исследований и разработок IBM . 3 (2): 114–125. дои : 10.1147/рд.32.0114 .

[2] Это определение было взято из конспектов лекций CS682 (Теория вычислений) Декстера Козена из Стэнфордского университета.

[3] Капуцис, Христос (2005). «Удаление двунаправленности из недетерминированных конечных автоматов». В Й. Енджейовиче, А. Шепетовском (ред.). Математические основы информатики . МФКС 2005. Том. 3618. Спрингер. стр. 544–555. дои : 10.1007/11549345_47 .

[LadnerLipton1984-4] Ладнер, Ричард Э.; Липтон, Ричард Дж.; Стокмейер, Ларри Дж. (1984). «Попеременные автоматы с выталкиванием и стекированием». SIAM Journal по вычислительной технике . 13 (1): 135–155. дои : 10.1137/0213010 . ISSN 0097-5397 .

[GeffertOkhotin2014-5] Гефферт, Вильям; Охотин, Александр (2014). «Преобразование двусторонних попеременных конечных автоматов в односторонние недетерминированные автоматы». Математические основы информатики 2014 . Конспекты лекций по информатике. Том. 8634. стр. 291–302. дои : 10.1007/978-3-662-44522-8_25 . ISBN 978-3-662-44521-1 . ISSN 0302-9743 .

[6] Сакода, Уильям Дж.; Сипсер, Майкл (1978). Недетерминизм и размер двусторонних конечных автоматов . СТОК 1978. ACM. стр. 275–286. дои : 10.1145/800133.804357 .

[7] Берман, Петр; Лингас, Анджей (1977). О сложности регулярных языков в терминах конечных автоматов . Том. Отчет 304. Польская академия наук.

[8] Капуцис, Христос А. (2014). «Двусторонние автоматы против логарифмического пространства». Теория вычислительных систем . 55 (2): 421–447. дои : 10.1007/s00224-013-9465-0 .

[9] Сипсер, Майкл (1980). «Нижние границы размера сметающих автоматов». Журнал компьютерных и системных наук . 21 (2): 195–202. дои : 10.1016/0022-0000(80)90034-3 .

[10] Джон Уотрус . О мощности двусторонних квантовых автоматов с конечным состоянием . CS-TR-1997-1350. 1997. PDF

[11] Джон Э. Хопкрофт; Джеффри Д. Уллман (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли. ISBN 978-0-201-02988-8 . Здесь: стр.124; этот абзац опущен в издании 2003 года.

[12] Дж. Хартманис; Премьер-министр Льюис II, Р.Э. Стернс (1965). «Иерархии вычислений с ограниченной памятью». Учеб. 6-я Энн. Симптом IEEE. по теории коммутационных цепей и логическому проектированию . стр. 179–190.

[13] Альфред В. Ахо; Джон Э. Хопкрофт; Джеффри Д. Уллман (1968). «Временная и ленточная сложность языков автоматов с pushdown» . Информация и контроль . 13 (3): 186–206. дои : 10.1016/s0019-9958(68)91087-5 .

[14] С. А. Кук (1971). «Моделирование детерминированных двусторонних автоматов с линейным временем». Учеб. Конгресс ИФИП . Северная Голландия. стр. 75–80.

[15] Джим Грей; Майкл А. Харрисон; Оскар Х. Ибарра (1967). «Автоматы с двусторонним нажатием». Информация и контроль . 11 (1–2): 30–70. дои : 10.1016/s0019-9958(67)90369-5 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]