Попеременный конечный автомат

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

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

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

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

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

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

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

Попеременный конечный автомат (AFA) — это набор из пяти чисел , $(Q,\Sigma ,q_{0},F,\delta )$ , где

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

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

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

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

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

Государственная сложность

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

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

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

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

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

Ссылки

^ Перейти обратно: ^а ^б Чандра, Ашок К.; Козен, Декстер К.; Стокмейер, Ларри Дж. (1981). «Чередование» . Журнал АКМ . 28 (1): 114–133. дои : 10.1145/322234.322243 . ISSN 0004-5411 .
^ Феллах, А.; Юргенсен, Х.; Ю, С. (1990). «Конструкции попеременных конечных автоматов∗». Международный журнал компьютерной математики . 35 (1–4): 117–132. дои : 10.1080/00207169008803893 . ISSN 0020-7160 .
^ Перейти обратно: ^а ^б Теорема 19 Хольцер, Маркус; Кутриб, Мартин (01 марта 2011 г.). «Описательная и вычислительная сложность конечных автоматов — обзор». Информация и вычисления . 209 (3): 456–470. дои : 10.1016/j.ic.2010.11.013 . ISSN 0890-5401 .

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

[ChandraKozen1981-1] Перейти обратно: ^а ^б Чандра, Ашок К.; Козен, Декстер К.; Стокмейер, Ларри Дж. (1981). «Чередование» . Журнал АКМ . 28 (1): 114–133. дои : 10.1145/322234.322243 . ISSN 0004-5411 .

[FellahJürgensen1990-2] Феллах, А.; Юргенсен, Х.; Ю, С. (1990). «Конструкции попеременных конечных автоматов∗». Международный журнал компьютерной математики . 35 (1–4): 117–132. дои : 10.1080/00207169008803893 . ISSN 0020-7160 .

[holzer2010descriptional-3] Перейти обратно: ^а ^б Теорема 19 Хольцер, Маркус; Кутриб, Мартин (01 марта 2011 г.). «Описательная и вычислительная сложность конечных автоматов — обзор». Информация и вычисления . 209 (3): 456–470. дои : 10.1016/j.ic.2010.11.013 . ISSN 0890-5401 .

[1]

[2]

[3]