! ! Principios de compilación DFA y NFA

DFA o NFA es un modelo abstracto del comportamiento de un programa informático. El programa que escribes en realidad corresponde a un autómata. Para un ejemplo simple, si a, b puede tomar el valor 0 o 1; programa: if (a==1) b=1 Este programa corresponde a un autómata.

El autómata correspondiente tiene los estados (0,0), (0,1), (1,1), (1, 0)

Por ejemplo, el estado inicial de su autómata Cuando el estado es (1,0), es decir, a = 1, b = 0, el siguiente estado del programa en ejecución es (1,1).

El dibujo muestra estos cuatro estados como vértices y las siguientes aristas

(0,0) --> (0,0) (autobucle), (1 ,0) -->(1,1), (1,1)-->(1,1) (autobucle), (0,1)-->(0,1) autobucle

El significado de la existencia es un modelo teórico, que también puede considerarse como una idea de programación. El sistema de análisis léxico también es inseparable de if else. Esta serie de if else y condiciones forman un autómata. . .

El algoritmo más clásico que encarna la idea de los autómatas es el algoritmo KMP. Debes haber aprendido el algoritmo de coincidencia de cadena-subcadena. Recuerde el proceso de este algoritmo: la siguiente tabla construida en el primer paso del algoritmo (en palabras del libro de texto de estructura de datos) en realidad construye un autómata basado en el contenido de la subcadena. El segundo paso del algoritmo utiliza la cadena original como entrada del autómata, y la salida del autómata es la posición de la subcadena coincidente o no coincide.