Autómata finito alternante

En la teoría de autómatas , un autómata finito alternante ( AFA ) es un autómata finito no determinista cuyas transiciones se dividen en transiciones existenciales y universales . Por ejemplo, sea A un autómata alternante .

• Para una transición existencial${\displaystyle (q,a,q_{1}\vee q_{2})}$, el autómata A elige de forma no determinista cambiar el estado a o${\displaystyle q_{1}}$o${\displaystyle q_{2}}$, al leer un . Por lo tanto, se comporta como un autómata finito no determinista regular .
• Para una transición universal${\displaystyle (q,a,q_{1}\wedge q_{2})}$, el autómata A se mueve a${\displaystyle q_{1}}$y${\displaystyle q_{2}}$, al leer un , simulando el comportamiento de una máquina paralela.

Nótese que, debido a la cuantificación universal, una secuencia se representa mediante un árbol de secuencias . A acepta una palabra w si existe un árbol de secuencias sobre w tal que cada ruta termina en un estado de aceptación.

Un teorema básico establece que cualquier AFA es equivalente a un autómata finito determinista (DFA); por lo tanto, los AFA aceptan exactamente los lenguajes regulares .

Un modelo alternativo que se usa con frecuencia es aquel en el que las combinaciones booleanas están en forma normal disyuntiva de modo que, por ejemplo,${\displaystyle \{\{q_{1}\},\{q_{2},q_{3}\}\}}$representaría${\displaystyle q_{1}\vee (q_{2}\wedge q_{3})}$. El estado tt ( verdadero ) está representado por${\displaystyle \{\emptyset \}}$en este caso y ff ( falso ) por${\displaystyle \emptyset }$Esta representación suele ser más eficiente.

Los autómatas finitos alternantes pueden extenderse para aceptar árboles de la misma manera que los autómatas de árboles , dando como resultado autómatas de árboles alternantes .

Un autómata finito alternante (AFA) es una 5-tupla , ${\displaystyle (Q,\Sigma ,q_{0},F,\delta )}$, dónde

• ${\displaystyle Q}$es un conjunto finito de estados;
• ${\displaystyle \Sigma }$es un conjunto finito de símbolos de entrada;
• ${\displaystyle q_{0}\in Q}$es el estado inicial (de inicio);
• ${\displaystyle F\subseteq Q}$es un conjunto de estados de aceptación (finales);
• ${\displaystyle \delta \colon Q\times \Sigma \times \{0,1\}^{Q}\to \{0,1\}}$es la función de transición.

Para cada cadena${\displaystyle w\in \Sigma ^{*}}$, definimos la función de aceptación${\displaystyle A_{w}\colon Q\to \{0,1\}}$por inducción sobre la longitud de${\displaystyle w}$:

• ${\displaystyle A_{\epsilon }(q)=1}$si${\displaystyle q\in F}$, y${\displaystyle A_{\epsilon }(q)=0}$de lo contrario;
• ${\displaystyle A_{aw}(q)=\delta (q,a,A_{w})}$.

El autómata acepta una cadena${\displaystyle w\in \Sigma ^{*}}$si y solo si${\displaystyle A_{w}(q_{0})=1}$.

Este modelo fue introducido por Chandra , Kozen y Stockmeyer . ^{[ 1 ]}

Aunque los autómatas finitos (AFA) pueden aceptar lenguajes regulares , se diferencian de otros tipos de autómatas finitos por la concisión de su descripción, medida por el número de sus estados.

Chandra et al. ^{[ 1 ]} demostraron que convertir un${\displaystyle n}$-Estado AFA a un DFA equivalente requiere${\displaystyle 2^{2^{n}}}$estados en el peor de los casos , aunque se puede construir un DFA para el lenguaje inverso con solo${\displaystyle 2^{n}}$estados. Otra construcción de Fellah, Jürgensen y Yu. ^{[ 2 ]} convierte un AFA con${\displaystyle n}$estados a un autómata finito no determinista (NFA) con hasta${\displaystyle 2^{n}}$estados mediante la realización de un tipo de construcción de conjunto potencia similar al utilizado para la transformación de un NFA en un DFA.

El problema de membresía pregunta, dado un AFA${\displaystyle A}$y una palabra${\displaystyle w}$, si${\displaystyle A}$acepta${\displaystyle w}$. Este problema es P-completo . ^{[ 3 ]} Esto es cierto incluso en un alfabeto unitario, es decir, cuando el autómata acepta un lenguaje unario .

El problema de no vacuidad (¿el lenguaje de un AFA de entrada no es vacío?), el problema de universalidad (¿el complemento del lenguaje de un AFA de entrada es vacío?) y el problema de equivalencia (¿dos AFA de entrada reconocen el mismo lenguaje?) son PSPACE-completos para AFA ^{[ 3 ] : Teoremas 23, 24, 25} .

• Pippenger, Nicholas (1997). Teorías de la computabilidad . Cambridge University Press . ISBN 978-0-521-55380-3.