Sabemos que los DFA son equivalentes a los NFA en poder de expresividad; También hay un algoritmo conocido para convertir NFA a DFA (desafortunadamente ahora conozco al inventor de ese algoritmo), que en el peor de los casos nos da estados, si nuestro NFA tenía estados.
Mi pregunta es: ¿qué determina el peor de los casos?
Aquí hay una transcripción de un algoritmo en caso de ambigüedad:
Deje que sea un NFA. Construimos un DFA dondeA ′ = ( Q ′ , Σ , δ ′ , q ′ 0 , F ′ )
- ,
- ,
- , y
- ,
donde es la función de transición prolongado de . A
Respuestas:
El algoritmo al que se refiere se llama Powerset Construction y fue publicado por primera vez por Michael Rabin y Dana Scott en 1959.
Para responder a su pregunta como se indica en el título, no existe un DFA máximo para un idioma normal, ya que siempre puede tomar un DFA y agregar tantos estados como desee con transiciones entre ellos, pero sin transiciones entre uno de los estados originales . y uno de los nuevos. Por lo tanto, los nuevos estados no serán accesibles desde el estado inicial , por lo que el idioma aceptado por el autómata no cambiará (ya que seguirá siendo el mismo para todos ) .δ ( q 0 , w ) w ∈ sigma *q0 0 δ^( q0 0, W ) w ∈ Σ∗
Dicho esto, está claro que no puede haber condiciones en un NFA para que su DFA equivalente sea máximo, ya que no hay un DFA equivalente único . En contraste, el DFA mínimo es único hasta el isomorfismo.
Un ejemplo canónico de un lenguaje aceptado por un NFA con estados con DFA equivalente de 2 n estados es L = { w ∈ { 0 , 1 } ∗ : | w | ≥ ny el n -ésimo símbolo del último es 1 } . A NFA para L es A = ⟨ Q , { 0 , 1 } , δ , q 0 , {n + 1 2norte
fuente
fuente
Creo que esta es una pregunta en la frontera del conocimiento, es decir, básicamente una pregunta de investigación. De una búsqueda rápida en Google, parece estar mayormente abierto. Además, durante muchos años he creído que es importante y vinculado a los límites inferiores de la teoría de la complejidad. No menciona directamente un análisis estadístico, pero eso es lo que implica su pregunta. Aquí hay dos ejemplos de estudios estadísticos sobre DFA / NFA que son similares para mostrar el enfoque general a preguntas de este tipo. Parece que la investigación empírica básica en preguntas como esta todavía está en su mayoría inexplorada. Es cierto que el segundo no se relaciona directamente con su pregunta, pero es lo más cercano que pude encontrar de la investigación actual.
Esta métrica estaría relacionada con las métricas de la teoría de grafos, como la densidad de bordes, etc. Probablemente exista alguna métrica de teoría de grafos muy importante o una combinación de métricas que calcule la "explosión" pero que no es obvia para mí de inmediato. Podría sugerir algo como métricas de colores de gráficos o métricas de camarilla tal vez. Luego, pruebe la métrica contra los dos conjuntos "explotar" versus "no explotar".
Otras respuestas a su pregunta hasta ahora solo dan un ejemplo de caso de "explosión" (útil para un estudio de caso) pero no abordan el tema clave de una métrica general.
Otra área para observar un programa de investigación empírica desarrollado con éxito es la investigación de puntos de transición SAT. Eso ha desarrollado vínculos muy profundos con los conceptos de física y termodinámica. Me parece probable que conceptos similares sean aplicables aquí. Por ejemplo, es probable que encuentre métricas de tipo de punto de transición análogas; probablemente densidad de bordes, etc. Observe paralelos con la teoría de compresibilidad de Kolmogorov.
También conjeturo que los NFA que "explotan" frente a aquellos que no lo son son análogos a los casos "difíciles" frente a "fáciles" de problemas de NP completo.
Otra forma más de estudiar este problema sería formular un problema de minimización de NFA. Es decir, dado un DFA, encontrar el NFA mínimo, que escuché por última vez (hace muchos años) todavía era un problema abierto.
[1] Sobre el rendimiento de los algoritmos de minimización de autómatas Marco Almeida, Nelma Moreira, Rogério Reis
[2] Autómatas que no reconocen palabras: un enfoque estadístico Cristian S. Calude, Cezar Câmpeanu, Monica Dumitrescu
fuente