Конечный автомат с переменным конечным числом

В теории автоматов альтернирующий конечный автомат ( АКА ) — это недетерминированный конечный автомат , переходы которого делятся на экзистенциальные и универсальные переходы. Например, пусть A — альтернирующий автомат .

• Для экзистенциального перехода A недетерминированно выбирает переключение состояния в одно из двух или , читая a . Таким образом, ведя себя как обычный недетерминированный конечный автомат . ${\displaystyle (q,a,q_{1}\vee q_{2})}$ ${\displaystyle q_{1}}$ ${\displaystyle q_{2}}$
• Для универсального перехода A переходит в и , считывая a , имитируя поведение параллельной машины. ${\displaystyle (q,a,q_{1}\wedge q_{2})}$ ${\displaystyle q_{1}}$ ${\displaystyle q_{2}}$

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

Основная теорема гласит, что любой АКА эквивалентен детерминированному конечному автомату (ДКА), поэтому АКА принимают только обычные языки .

Альтернативная модель, которая часто используется, — это та, в которой булевы комбинации находятся в дизъюнктивной нормальной форме, так что, например, будет представлять . Состояние tt ( true ) представлено в этом случае как , а ff ( false ) как . Такое представление обычно более эффективно. ${\displaystyle \{\{q_{1}\},\{q_{2},q_{3}\}\}}$ ${\displaystyle q_{1}\vee (q_{2}\wedge q_{3})}$ ${\displaystyle \{\emptyset \}}$ ${\displaystyle \emptyset }$

Альтернативные конечные автоматы могут быть расширены для принятия деревьев таким же образом, как и древовидные автоматы , что даст альтернативные древовидные автоматы .

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

Альтернирующий конечный автомат (АКА) — это 5-кортеж , где ${\displaystyle (Q,\Sigma ,q_{0},F,\delta )}$

• ${\displaystyle Q}$— конечный набор состояний;
• ${\displaystyle \Sigma }$— конечный набор входных символов;
• ${\displaystyle q_{0}\in Q}$— начальное (стартовое) состояние;
• ${\displaystyle F\subseteq Q}$представляет собой набор принимающих (конечных) состояний;
• ${\displaystyle \delta \colon Q\times \Sigma \times \{0,1\}^{Q}\to \{0,1\}}$— это функция перехода.

Для каждой строки мы определяем функцию принятия индукцией по длине : ${\displaystyle w\in \Sigma ^{*}}$ ${\displaystyle A_{w}\colon Q\to \{0,1\}}$ ${\displaystyle w}$

• ${\displaystyle A_{\epsilon }(q)=1}$если , а в противном случае; ${\displaystyle q\in F}$ ${\displaystyle A_{\epsilon }(q)=0}$
• ${\displaystyle A_{aw}(q)=\delta (q,a,A_{w})}$.

Автомат принимает строку тогда и только тогда, когда . ${\displaystyle w\in \Sigma ^{*}}$ ${\displaystyle A_{w}(q_{0})=1}$

Эта модель была представлена ​​Чандрой , Козеном и Стокмейером . ^[1]

Сложность состояния

Несмотря на то, что АФА могут принимать именно регулярные языки , они отличаются от других типов конечных автоматов краткостью описания, измеряемой числом их состояний.

Чандра и др. ^[1] доказали, что преобразование AFA с -состояниями в эквивалентный DFA требует состояний в худшем случае, хотя DFA для обратного языка может быть построен только с состояниями. Другая конструкция Феллаха, Юргенсена и Ю. ^[2] преобразует AFA с состояниями в недетерминированный конечный автомат (NFA) с до состояний, выполняя подобный вид построения powerset, который используется для преобразования NFA в DFA. ${\displaystyle n}$ ${\displaystyle 2^{2^{n}}}$ ${\displaystyle 2^{n}}$ ${\displaystyle n}$ ${\displaystyle 2^{n}}$

Сложность вычислений

Проблема членства спрашивает, при наличии AFA и слова , принимает ли . Эта проблема является P-полной . ^[3] Это верно даже для одноэлементного алфавита, т. е. когда автомат принимает унарный язык . ${\displaystyle A}$ ${\displaystyle w}$ ${\displaystyle A}$ ${\displaystyle w}$

Проблема непустоты (является ли язык входного AFA непустым?), проблема универсальности (является ли дополнение языка входного AFA пустым?) и проблема эквивалентности (распознают ли два входных AFA один и тот же язык) являются PSPACE-полными для AFA ^{[3] : теоремы 23, 24, 25} .

Ссылки

1. Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). «Alternation». Journal of the ACM . 28 (1): 114–133. doi : 10.1145/322234.322243 . ISSN  0004-5411.
2. Феллах, А.; Юргенсен, Х.; Ю, С. (1990). «Конструкции для чередующихся конечных автоматов∗». Международный журнал компьютерной математики . 35 (1–4): 117–132. doi :10.1080/00207169008803893. ISSN  0020-7160.
3. Теорема 19 Хольцера, Маркуса; Кутриба, Мартина (2011-03-01). «Описательная и вычислительная сложность конечных автоматов — обзор». Информация и вычисления . 209 (3): 456–470. doi :10.1016/j.ic.2010.11.013. ISSN  0890-5401.

• Пиппенджер, Николас (1997). Теории вычислимости . Cambridge University Press . ISBN 978-0-521-55380-3.