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

В теории автоматов альтернирующий конечный автомат ( АКА ) — это недетерминированный конечный автомат , переходы которого делятся на экзистенциальные и универсальные переходы. Например, пусть 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} .

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