Переменный конечный автомат - Alternating finite automaton

В теории автоматов , переменные конечный автомат ( AFA ) является недетерминированными конечными автоматами , чьи переходы делятся на экзистенциальные и универсальные переходы. Например, пусть A - знакопеременный автомат .

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

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

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

Часто используется альтернативная модель, в которой логические комбинации представлены в виде предложений . Например, можно было бы предположить, что комбинации находятся в дизъюнктивной нормальной форме, так что это будет представлять . Состояние tt ( истина ) в этом случае представлено как, а состояние ff ( ложь ) - как . Представление этого предложения обычно более эффективно. ${\ Displaystyle \ {\ {q_ {1} \}, \ {q_ {2}, q_ {3} \} \}}$${\ displaystyle q_ {1} \ vee (q_ {2} \ wedge q_ {3})}$${\ Displaystyle \ {\ emptyset \}}$${\ displaystyle \ emptyset}$

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

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

Знакопеременный конечный автомат (AFA) - это набор из 6 , где ${\ Displaystyle (S (\ существует), S (\ forall), \ Sigma, \ delta, P_ {0}, F)}$

• ${\ Displaystyle S (\ существует)}$конечный набор экзистенциальных состояний. Также обычно обозначается как .${\ Displaystyle S (\ vee)}$
• ${\ Displaystyle S (\ forall)}$- конечный набор универсальных состояний. Также обычно обозначается как .${\ Displaystyle S (\ клин)}$
• ${\ Displaystyle \ \ Sigma}$ - конечный набор входных символов.
• ${\ displaystyle \ \ delta}$набор отношений перехода к следующему состоянию .${\ Displaystyle (S (\ существует) \ чашка S (\ forall)) \ раз (\ Sigma \ cup \ {\ varepsilon \}) \ to 2 ^ {S (\ exists) \ cup S (\ forall)}}$
• ${\ Displaystyle \ P_ {0}}$- начальное (стартовое) состояние, такое что .${\ Displaystyle P_ {0} \ в S (\ существует) \ чашка S (\ forall)}$
• ${\ Displaystyle \ F}$- это набор принимающих (конечных) состояний, таких что .${\ Displaystyle F \ substeq S (\ существует) \ чашка S (\ forall)}$

Модель была представлена Chandra , Kozen и Stockmeyer .

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

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

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

Вычислительная сложность

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

Проблема непустоты (является ли язык входного AFA непустым?), Проблема универсальности (является ли дополнение языка входного AFA пустым?) И проблема эквивалентности (распознают ли два входных AFA один и тот же язык ) являются PSPACE-полными для AFA.

Рекомендации

• Пиппенгер, Николас (1997). Теории вычислимости . Издательство Кембриджского университета . ISBN 978-0-521-55380-3.