Flex
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...
Regístrate para leer el documento completo.