En la teoría de autómatas , un autómata finito inequívoco ( UFA ) es un autómata finito no determinista (NFA) de modo que cada palabra tiene como máximo un camino de aceptación. Cada autómata finito determinista (DFA) es un UFA, pero no al revés. DFA, UFA y NFA reconocen exactamente la misma clase de lenguajes formales . Por un lado, un NFA puede ser exponencialmente más pequeño que un DFA equivalente. Por otro lado, algunos problemas se resuelven fácilmente en DFA y no en UFA. Por ejemplo, dado un autómata A , un autómata A ′ que acepta el complemento de A se puede calcular en tiempo lineal cuando Aes un DFA, no se sabe si se puede hacer en tiempo polinomial para UFA. Por lo tanto, los UFA son una mezcla de los mundos de DFA y NFA; en algunos casos, conducen a autómatas más pequeños que DFA y algoritmos más rápidos que NFA.
Definicion formal
Un NFA está representado formalmente por una tupla de 5 , A = ( Q , Σ, Δ, q 0 , F ). Un UFA es un NFA tal que, para cada palabra w = a 1 a 2 … a n , existe como máximo una secuencia de estados r 0 , r 1 ,…, r n , en Q con las siguientes condiciones:
- r 0 = q 0
- r i + 1 ∈ Δ ( r i , a i + 1 ), para i = 0,…, n − 1
- r n ∈ F .
En palabras, esas condiciones establecen que, si w es aceptado por A , hay exactamente un camino de aceptación, es decir, un camino desde un estado inicial a un estado final, etiquetado por w .
Ejemplo
Let L el conjunto de palabras sobre el alfabeto { a , b } cuyos n º última letra es una una . Las figuras muestran un DFA y un UFA que aceptan este idioma para n = 2 .
El DFA mínimo que acepta L tiene 2 n estados, uno para cada subconjunto de {1 ... n }. Hay un UFA de n +1 estados que acepta L : adivina la n- ésima última letra y luego verifica que solo quedan n -1 letras. De hecho, es ambigua, ya que sólo existe una n º última carta.
Inclusión, universalidad, equivalencia
Tres problemas difíciles de PSPACE para NFA generales pertenecen a PTIME para DFA y ahora se consideran.
Inclusión
Es decidible en tiempo polinomial si el idioma de un UFA es un subconjunto del idioma de otro UFA.
Boceto de la prueba de inclusión |
---|
Sean A y B dos UFA. Sean L ( A ) y L ( B ) los lenguajes aceptados por esos autómatas. Entonces L ( A ) ⊆ L ( B ) si y solo si L ( A ∩ B ) = L ( A ), donde A ∩ B denota el producto autómata cartesiano, que puede demostrarse que también es inequívoco. Ahora, L ( A ∩ B ) es un subconjunto de L ( A ) por construcción; por tanto, ambos conjuntos son iguales si y solo si para cada longitud n ∈ℕ, el número de palabras de longitud n en L ( A ∩ B ) es igual al número de palabras de longitud n en L ( A ). Se puede demostrar que es suficiente para comprobar cada n hasta el producto del número de estados de A y B . El número de palabras de longitud n aceptadas por un autómata se puede calcular en tiempo polinomial utilizando programación dinámica , que finaliza la demostración. [1] |
Universalidad, equivalencia
El problema de la universalidad [nota 1] y de la equivalencia, [nota 2] también pertenecen al PTIME , por reducción al problema de la inclusión.
Comprobando si un autómata es inequívoco
Para un autómata finito no determinista A con n estados y un alfabeto de m letras, es decidible en el tiempo O (n 2 m) si A es inequívoco. [2]
Bosquejo de la prueba de la inequívoca |
---|
Basta utilizar un algoritmo de punto fijo para calcular el conjunto de pares de estados q y q 'de manera que exista una palabra w que conduzca tanto a q como a q' . El autómata es inequívoco si y solo si no existe un par tal que ambos estados lo acepten. Hay pares de estados Θ ( n 2 ), y para cada par hay m letras a considerar para reanudar el algoritmo de punto fijo, de ahí el tiempo de cálculo. |
Algunas propiedades
- El producto cartesiano de dos UFA es un UFA. [3]
- La noción de no ambigüedad se extiende a los transductores de estado finito y a los autómatas ponderados . Si un transductor de estado finito T no es ambiguo, entonces cada palabra de entrada está asociada por T a como máximo una palabra de salida. Si un autómata ponderado A es inequívoco, entonces el conjunto de pesos no necesita ser un semirrígido , sino que basta con considerar un monoide . De hecho, hay como máximo un camino de aceptación.
Complejidad del estado
Las pruebas matemáticas de que cada UFA para un idioma necesita un cierto número de estados fueron pioneras en Schmidt. [4] Leung demostró que un DFA equivalente a un-Estado UFA requiere afirma en el peor de los casos, y que un UFA equivalente a un finitamente ambiguo [nota 3] -Estado NFA requiere estados en el peor de los casos. [5]
Jirásek, Jirásková y Šebej [6] investigaron la complejidad estatal de operaciones regulares básicas en lenguajes representados por UFA. Demostraron en particular que para cada-estado UFA donde , el complemento del idioma que acepta es aceptado por una UFA con como máximo estados. Este resultado fue posteriormente mejorado por Indzhev y Kiefer [7] a lo sumo estados para todos .
Para un alfabeto de una letra, Okhotin demostró que un DFA equivalente a un -Estado UFA requiere estados en el peor de los casos. [8]
Notas
Referencias
- Christof Löding, Autómatas finitos inequívocos , Desarrollos en la teoría del lenguaje , (2013) págs. 29-30 ( diapositivas )
- ^ Christof Löding, Autómatas finitos inequívocos , Diapositiva 8
- ^ Sakarovitch, Jacques; Thomas, Rubén. Elementos de la teoría de los autómatas . Cambridge: prensa de la universidad de Cambridge. pag. 75. ISBN 978-0-521-84425-3.
- ^ Christof Löding, Autómatas finitos inequívocos , Diapositiva 8
- ^ Schmidt, Erik M. (1978). Concisión de la descripción de lenguajes libres de contexto, regulares e inequívocos (Ph.D.). Universidad de Cornell.
- ^ Leung, Hing (2005). "Complejidad descriptiva de NFA de diferente ambigüedad". Revista Internacional de Fundamentos de la Ciencia de la Computación . 16 (05): 975–984. doi : 10.1142 / S0129054105003418 . ISSN 0129-0541 .
- ^ Jirásek, Jozef; Jirásková, Galina; Šebej, Juraj (2016). "Operaciones en autómatas finitos inequívocos". 9840 : 243-255. doi : 10.1007 / 978-3-662-53132-7_20 . ISSN 0302-9743 . Cite journal requiere
|journal=
( ayuda ) - ^ Indzhev, Emil; Kiefer, Stefan (2021). "Sobre la complementación de autómatas y gráficos inequívocos con muchas camarillas y cocliques". arXiv : 2105.07470 [ cs.FL ].
- ^ Okhotin, Alexander (2012). "Autómatas finitos inequívocos sobre un alfabeto unario" . Información y Computación . 212 : 15–36. doi : 10.1016 / j.ic.2012.01.003 . ISSN 0890-5401 .