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

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.

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.

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.

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).