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 .
- Por una transición existencial , A de forma no determinista elige cambiar el estado a o , leyendo un . Por lo tanto, comportarse como un autómata finito no determinista regular .
- Por una transición universal , A se mueve a y , leyendo a , simulando el comportamiento de una máquina paralela.
Tenga en cuenta que, debido a la cuantificación universal, una ejecución se representa mediante un árbol de ejecución . A acepta una palabra w , si existe un árbol de ejecución en w tal que cada ruta termine 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 se representan como cláusulas . Por ejemplo, se podría suponer que las combinaciones están en forma normal disyuntiva de modo que representaría . El estado tt ( verdadero ) está representado poren este caso y ff ( falso ) por. Esta representación de cláusulas suele ser más eficaz.
Los autómatas finitos alternos se pueden ampliar para aceptar árboles de la misma manera que los autómatas de árbol , lo que produce autómatas de árbol alternos .
Definicion formal
Un autómata finito alterno (AFA) es una tupla de 6 ,, dónde
- es un conjunto finito de estados existenciales. También comúnmente representado como.
- es un conjunto finito de estados universales. También comúnmente representado como.
- es un conjunto finito de símbolos de entrada.
- es un conjunto de relaciones de transición al siguiente estado .
- es el estado inicial (inicio), tal que .
- es un conjunto de estados aceptables (finales) tales que .
El modelo fue presentado 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 y col. [1] demostró que convertir un-Estado AFA a un DFA equivalente requiere estados en el peor de los casos. Otra construcción de Fellah, Jürgensen y Yu. [2] convierte una AFA conestados a un autómata finito no determinista (NFA) con hasta estados mediante la realización de un tipo de construcción de conjunto de potencia similar al utilizado para la transformación de un NFA en un DFA.
Complejidad computacional
El problema de la membresía pregunta, dada una AFA y una palabra , ya sea 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 .
El problema de no vacío (¿el lenguaje de un AFA de entrada no está vacío?), El problema de universalidad (¿el complemento del lenguaje de un AFA de entrada está vacío?) Y el problema de equivalencia (¿dos AFA de entrada reconocen el mismo idioma ) son PSPACE-completos para AFA [3] : Teoremas 23, 24, 25 .
Referencias
- ^ a b 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 .
- ^ 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 .
- ^ a b Teorema 19 de Holzer, Markus; Kutrib, Martin (1 de marzo de 2011). "Complejidad descriptiva y computacional de autómatas finitos: una encuesta" . 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 . Prensa de la Universidad de Cambridge . ISBN 978-0-521-55380-3.