Autómata finito alterno

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

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

Tenga en cuenta que debido a la cuantificación universal, una serie se representa mediante un árbol de series . A acepta una palabra w si existe un árbol de series en 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 utiliza con frecuencia es aquel en el que las combinaciones booleanas están en forma normal disyuntiva , de modo que, por ejemplo, representaría . El estado tt ( verdadero ) se representa en este caso con y ff ( falso ) con . Esta representación suele ser más eficiente. ${\displaystyle \{\{q_{1}\},\{q_{2},q_{3}\}\}}$ ${\displaystyle q_{1}\vee (q_{2}\wedge q_{3})}$ ${\displaystyle \{\emptyset \}}$ ${\displaystyle \emptyset }$

Los autómatas finitos alternos se pueden extender para aceptar árboles de la misma manera que los autómatas de árbol , lo que produce autómatas de árbol alternos .

Definición formal

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

• ${\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 , definimos la función de aceptación por inducción sobre la longitud de : ${\displaystyle w\in \Sigma ^{*}}$ ${\displaystyle A_{w}\colon Q\to \{0,1\}}$ ${\displaystyle w}$

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

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

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

Complejidad del estado

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

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

Complejidad computacional

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

El problema de no vacío (¿el lenguaje de un AFA de entrada es no 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 los AFA ^{[3] : Teoremas 23, 24, 25} .

Referencias

1. Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). "Alternancia". Revista de la ACM . 28 (1): 114–133. doi : 10.1145/322234.322243 . ISSN  0004-5411.
2. Fellah, A.; Jürgensen, H.; Yu, S. (1990). "Construcciones para autómatas finitos alternos∗". Revista Internacional de Matemáticas Informáticas . 35 (1–4): 117–132. doi :10.1080/00207169008803893. ISSN  0020-7160.
3. Teorema 19 de Holzer, Markus; Kutrib, Martin (1 de marzo de 2011). "Complejidad descriptiva y computacional de autómatas finitos: un estudio". Información y computación . 209 (3): 456–470. doi :10.1016/j.ic.2010.11.013. ISSN  0890-5401.

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