¿Se puede convertir eficientemente un autómata finito no determinista (NDFA) en un autómata finito determinista (DFA) en espacio / tiempo subexponencial?

16

Hace veinte años, creé un paquete de expresiones regulares que incluía conversiones de expresiones regulares a una máquina de estados finitos (DFA) y soportaba una gran cantidad de operaciones de expresiones regulares cerradas (estrella de Kleene, concatenación, operaciones inversas, de configuración, etc.). No estaba seguro sobre el peor desempeño de mi paquete.

Un DFA tiene el mismo poder expresivo que un NDFA, porque un NDFA de estado n puede convertirse trivialmente en un DFA que tiene 2 ^ n estados. Sin embargo, ¿existen garantías de límite superior inferior para dicha conversión que no requieran una explosión de estado exponencial?

No pude encontrar ejemplos de expresiones regulares de mal comportamiento o NDFA, pero no pasé mucho tiempo pensando en ello. Estoy adivinando una expresión regular como (((((e | A | B | C) * (e | D | E | F)) * (e | G | H | I)) * (e | J | K | L | M)) * que mezcla muchas alternancias y las estrellas de Kleene tendrían un NDFA de tamaño lineal pero un DFA expansivo.

Wesner Moise
fuente
¿Hay alguna restricción en la clase de NFA que le gustaría aceptar como entrada? Algunas restricciones conducen a mejores límites superiores.
András Salamon
no es un punto muy importante, pero ¿necesita ndfa ser su propia etiqueta?
Lev Reyzin
Si hay restricciones. Los NFA se construyen directamente a partir de expresiones regulares al tratarlos como gráficos de transición generalizados. seas.upenn.edu/~cit596/notes/dave/regexp-nfa4.html
Wesner Moise

Respuestas:

15

Se sabe que para cada par de números naturales de n,atal manera n <= a <= 2^n, existe un NDFA mínimo con nestados cuyo dfa mínimo equivalente correspondiente tiene aestados (sobre un alfabeto de cuatro letras).

Vea el artículo aquí: ampliaciones deterministas de autómatas finitos no deterministas mínimos sobre un alfabeto fijo .

Resumen del artículo:

Mostramos que para todos los enteros n y α de manera que n ≤ α ≤ 2 ^ n, existe un autómata finito no determinista mínimo de n estados con un alfabeto de entrada de cuatro letras cuyo autómata finito determinista mínimo equivalente tiene exactamente un estado. Se deduce que en el caso de un alfabeto de cuatro letras, no hay "números mágicos", es decir, los agujeros en la jerarquía. Esto mejora un resultado similar obtenido por Geffert para un alfabeto en crecimiento de tamaño n + 2 (Procedimiento 7º DCFS, Como, Italia, 23-37).

Entonces, supongo que la respuesta a su pregunta es no.

Aryabhata
fuente
la pregunta es pedir un "algoritmo" que se ejecute en tiempo y espacio subexponencial para convertir el NFA.
Marcos Villagra
@Marcos: si su salida es exponencial, no es posible que tenga un algoritmo que se ejecute en tiempo sub-exponencial.
Aryabhata
1
Este es un resultado general. Si existen restricciones conocidas en la clase de NFA de entrada, entonces podría ser posible hacerlo mejor.
András Salamon
@Andras: De acuerdo, pero dado que esto probablemente esté relacionado con la programación (que admitirá Kleen *, etc.), dudo que el conjunto de NFA de entrada esté restringido a un subconjunto adecuado.
Aryabhata
55
Este resultado se fortaleció recientemente para usar un alfabeto de tres letras, y las construcciones son un poco más simples: portal.acm.org/…
13

El ejemplo clásico para un lenguaje con una separación exponencial entre el tamaño de DFA y el tamaño de NFA es el siguiente lenguaje finito: cadenas binarias de longitud exactamente 2n en las que la primera mitad no es igual a la segunda mitad. Un NFA adivinaría un índice i en el que la primera y la segunda mitad no están de acuerdo. Un límite inferior para un DFA se deriva de la complejidad de la comunicación, por ejemplo.

Noam
fuente
8

El DFA mínimo correspondiente a un NFA tiene 2 ^ n estados en el peor de los casos, por lo que no puede garantizar nada. Sin tener un ejemplo constructivo, el razonamiento es que en un NFA puede estar en cualquier subconjunto arbitrario de estados después de leer una determinada cadena de entrada, y cada subconjunto podría comportarse de manera diferente al observar un carácter. Supongamos un lenguaje con dos caracteres en el alfabeto (ayb), y un NFA N con n estados que comienza con un estado de aceptación en s_0. Ahora enumere todos los subconjuntos de estados de N y construya la tabla de transición de modo que observar "a" desde el subconjunto S_i lo lleve al subconjunto S_i + 1 y observar b lo lleve al subconjunto S_i-1 (creo que esto es factible para algunas enumeraciones, creo ) Ahora este autómata tiene n estados y acepta secuencias de ma y nb de tal manera que mn = 0 mod 2 ^ | N |, y no se puede expresar con un DFA que tenga menos de 2 ^ | N | estados (ya que podría necesitar recorrer todos los subconjuntos de estados de la NFA N).

Alexandre Passos
fuente
¿Se puede convertir esto en un argumento que diga "si (algo malo) se evita en el NFA, entonces el DFA tiene un número subexponencial de estados"?
András Salamon
1
@ András, sí. "Si se evita el no determinismo en el NFA, entonces el DFA tiene un número subexponencial de estados".
P Shved
2
Pavel, sí, obviamente. ¿Existe alguna propiedad no trivial que pueda reconocerse de manera eficiente que también garantice una explosión subexponencial?
András Salamon