Autómata finito inequívoco

En la teoría de autómatas , un autómata finito unívoco ( UFA ) es un autómata finito no determinista (NFA) tal que cada palabra tiene como máximo una ruta 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 A es un DFA, mientras que se sabe que esto no se puede hacer en tiempo polinomial para UFA. Por lo tanto, los UFA son una mezcla de los mundos de DFA y de NFA; en algunos casos, conducen a autómatas más pequeños que DFA y algoritmos más rápidos que NFA.

Definición formal

Un NFA se representa formalmente mediante una 5-tupla , . Un UFA es un NFA tal que, para cada palabra , existe como máximo una secuencia de estados , en con las siguientes condiciones: ${\displaystyle A=(Q,\Sigma ,\Delta ,q_{0},F)}$ ${\displaystyle w=a_{1}a_{2}...a_{n}}$ ${\displaystyle r_{0},r_{1},...,r_{n}}$ ${\displaystyle Q}$

1. ${\displaystyle r_{0}=q_{0}}$;
2. ${\displaystyle r_{i+1}\in \Delta (r_{i},a_{i+1})}$para ; ${\displaystyle i=0,...n-1}$
3. ${\displaystyle r_{n}\in F}$.

En palabras, esas condiciones establecen que, si es aceptado por , hay exactamente un camino de aceptación, es decir, un camino desde un estado inicial a un estado final que está etiquetado por . ${\displaystyle w}$ ${\displaystyle A}$ ${\displaystyle w}$

Ejemplo

Sea el conjunto de palabras sobre el alfabeto { a , b } cuya n ª última letra es an . Las figuras muestran un DFA y un UFA que aceptan este idioma para n=2 . ${\displaystyle L}$ ${\displaystyle a}$

Autómata determinista (DFA) para el lenguaje L para n=2

Autómata finito inequívoco (AFU) para el lenguaje L para n=2

El DFA mínimo que acepta tiene 2 ⁿ estados, uno para cada subconjunto de {1... n }. Hay un UFA de estados que acepta : adivina la n- ésima última letra y luego verifica que solo queden letras. De hecho, no es ambiguo ya que solo existe una n- ésima última letra. ${\displaystyle L}$ ${\displaystyle n+1}$ ${\displaystyle L}$ ${\displaystyle n-1}$

Inclusión, universalidad, equivalencia

Tres problemas PSPACE -hard para NFA general pertenecen a PTIME para DFA y ahora se consideran.

Inclusión

Es decidible en tiempo polinomial si el idioma de una UFA es un subconjunto del idioma de otra UFA.

Universalidad, equivalencia

El problema de la universalidad ^{[nota 1]} y de la equivalencia ^{[nota 2]} también pertenecen a PTIME , por reducción al problema de inclusión.

Comprobación de si un autómata es inequívoco

Para un autómata finito no determinista con estados y un alfabeto de letras, es decidible en el tiempo si es inequívoco. ^[2] ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle O(n^{2}m)}$ ${\displaystyle A}$

Algunas propiedades

• Dado un UFA A y un entero n , se puede contar en tiempo polinomial la cantidad de palabras de tamaño n que son aceptadas por A . Esto se puede hacer mediante un algoritmo de programación dinámica simple: para cada estado q de A y , calcular la cantidad de palabras de tamaño ni que tienen una serie que comienza en q y termina en un estado final. Por el contrario, el mismo problema es #P-hard para los NFA. ${\displaystyle i\in \{0,\ldots ,n\}}$
• El producto cartesiano (intersección) de dos AFU es un AFU. ^[3]
• La noción de uniambigüedad se extiende a los transductores de estados finitos y a los autómatas ponderados . Si un transductor de estados finitos T es uniambiguo, entonces cada palabra de entrada está asociada por T a , como máximo, una palabra de salida. Si un autómata ponderado A es uniambiguo, entonces el conjunto de pesos no necesita ser un semiring , 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 lenguaje necesita una cierta cantidad de estados fueron iniciadas por Schmidt. ^[4] Leung demostró que un DFA equivalente a un UFA de -estado requiere estados en el peor de los casos, y que un UFA equivalente a un NFA de -estado finitamente ambiguo ^{[nota 3]} requiere estados en el peor de los casos. ^[5] ${\displaystyle n}$ ${\displaystyle 2^{n}}$ ${\displaystyle n}$ ${\displaystyle 2^{n}-1}$

Jirásek, Jirásková y Šebej ^[6] investigaron la complejidad de estados de las operaciones regulares básicas en lenguajes representados por AFU. Demostraron en particular que para cada AFU de estado donde , el complemento del lenguaje que acepta es aceptado por un AFU con como máximo estados. Este resultado fue mejorado posteriormente por Indzhev y Kiefer ^[7] a como máximo estados para todos los . ${\displaystyle n}$ ${\displaystyle n\geq 7}$ ${\displaystyle 2^{0.79n+\log n}}$ ${\displaystyle {\sqrt {n+1}}\cdot 2^{0.5n}}$ ${\displaystyle n\geq 0}$

Raskin ^[8] demostró que los UFA no pueden complementarse en tiempo polinómico, ni siquiera en NFA: demuestra que, en el peor de los casos, complementar un UFA con n estados en un NFA requiere un número superpolinómico de estados. Esta cota inferior fue mejorada posteriormente por Göös, Kiefer y Yuan. ^[9]

Para un alfabeto de una sola letra, Okhotin demostró que un DFA equivalente a un UFA de -estado requiere estados en el peor de los casos. ^[10] ${\displaystyle n}$ ${\displaystyle \exp \left(\Theta \left({\sqrt[{3}]{n(\ln n)^{2}}}\right)\right)}$

Notas

1. es decir: dado un UFA, ¿acepta cada cadena de Σ ^* ?
2. es decir: dadas dos UFA, ¿aceptan el mismo conjunto de cadenas?
3. Tener un número finito de caminos de aceptación para cada palabra aceptada.

Referencias

• Christof Löding, Autómatas finitos inequívocos , Desarrollos en la teoría del lenguaje , (2013), págs. 29-30 (diapositivas)

1. Christof Löding, Autómatas finitos inequívocos , diapositiva 8
2. Sakarovitch, Jacques; Thomas, Reuben (octubre de 2009). Elementos de la teoría de autómatas . Cambridge: Cambridge University Press. pág. 75. ISBN. 978-0-521-84425-3.
3. Christof Löding, Autómatas finitos inequívocos , diapositiva 8
4. Schmidt, Erik M. (1978). Concisión en la descripción de lenguajes libres de contexto, regulares y no ambiguos (Ph.D.). Universidad de Cornell.
5. Leung, Hing (2005). "Complejidad descriptiva de NFA de diferente ambigüedad". Revista Internacional de Fundamentos de la Ciencia de la Computación . 16 (5): 975–984. doi :10.1142/S0129054105003418. ISSN  0129-0541.
6. Jirásek, Jozef; Jirásková, Galina; Šebej, Juraj (2016). "Operaciones sobre autómatas finitos inequívocos". Desarrollos en la teoría del lenguaje . Apuntes de conferencias sobre informática. vol. 9840, págs. 243–255. doi :10.1007/978-3-662-53132-7_20. ISBN 978-3-662-53131-0. ISSN  0302-9743.
7. Indzhev, Emil; Kiefer, Stefan (2021). "Sobre la complementación de autómatas y grafos inequívocos con muchas camarillas y coclicas". arXiv : 2105.07470 [cs.FL].
8. Raskin, Mikhail (2018). "Un límite inferior superpolinomial para el tamaño del complemento no determinista de un autómata inequívoco". DROPS-IDN/V2/Document/10.4230/LIPIcs.ICALP.2018.138 . Schloss-Dagstuhl - Leibniz Zentrum für Informatik. doi : 10.4230/LIPIcs.ICALP.2018.138 .
9. Göös, Mika; Kiefer, Stefan; Yuan, Weiqiang (2022). "Límites inferiores para autómatas inequívocos a través de la complejidad de la comunicación". DROPS-IDN/V2/Document/10.4230/LIPIcs.ICALP.2022.126 . Schloss-Dagstuhl - Leibniz Zentrum für Informatik. doi : 10.4230/LIPIcs.ICALP.2022.126 .
10. 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.