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

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

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

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

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

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

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

Альтернативный конечный автомат (AFA) - это 6-кратный,${\displaystyle (S(\exists ),S(\forall ),\Sigma ,\delta ,P_{0},F)}$, куда

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

Модель была представлена Чандра, Козен и Stockmeyer.^[1]

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

Основная статья: Сложность состояния

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

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

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

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

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

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

1. Chandra, Ashok K .; Kozen, Dexter C .; Стокмейер, Ларри Дж. (1981). «Чередование». Журнал ACM. 28 (1): 114–133. Дои:10.1145/322234.322243. ISSN  0004-5411.
2. Fellah, A .; Jürgensen, H .; Ю. С. (1990). «Конструкции для знакопеременных конечных автоматов ∗». Международный журнал компьютерной математики. 35 (1–4): 117–132. Дои:10.1080/00207169008803893. ISSN  0020-7160.
3. Теорема 19 из Хольцер, Маркус; Кутриб, Мартин (01.03.2011). «Описание и вычислительная сложность конечных автоматов. Обзор». Информация и вычисления. 209 (3): 456–470. Дои:10.1016 / j.ic.2010.11.013. ISSN  0890-5401.

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