Flex

Ana Aide Morquecho Delgadillo

Los NFA’s tiene la habilidad de poder estar en varios estados diferentes al mismo tiempo. Son más sencillos de diseñar que los DFA’s. Siempre se puede convertir unNFA a un DFA Notación: Consiste en : 1. Un conjunto finito de estados denotado por Q 2. Un conjunto finito de símbolos externos (inputs) denotado por ∑ 3. Una función de transición denotada por , quetoma como argumentos un estado y un símbolo externo, y devuelve un subconjunto de Q 4. Un estado inicial 5. Un conjunto de estados finales denotado por F, donde F СQ

DFA

NFA

Ejemplo 2: NFAque acepta solamente todas las cadenas de ceros y unos que finalizan en 01. Los estados son: 1. q0: no ha comenzado a verse el \01" del final de la cadena. 2. q1: se introdujo el 0 del \01" del finalde la cadena. 3. q2: se introdujo el 1 del \01" del final de la cadena. El autómata se denota formalmente por: ( {q0,q1,q2}, {0,1}, , q0, {q2} )

Diagrama de transiciones para el autómata

Tablade transiciones para el autómata

La función de transición toma un estado q y un estímulo a y devuelve un conjunto de estados

4. Hasta aquí todos los estados son accesibles y ya no surgennuevos estados por tanto termina el proceso

Método 2: •Eliminar transiciones ԑ como las transiciones múltiples de un estado con una entrada de carácter simple (algoritmo de construcción desubconjuntos) •Para eliminar las transiciones ԑ se deben construir cerraduras ԑ, las cuales son el conjunto de todos los estados que pueden alcanzar las transiciones ԑ desde un estado o estados •La eliminaciónde transiciones múltiples de un estado con una entrada simple implica mantenerse al tanto del conjunto de estados que so alcanzables al igualar un carácter simple

Cerradura ԑ de un conjunto deestados: se define la cerradura ԑ de un estado simple s como el conjunto de estados alcanzables por una serie de cero o mas transiciones ԑ, y se escribe este conjunto como s barra. Advierta que la...