Autómatas

Tema - Autómatas

Transiciones Lambda: Una transición lambda es aquella que permite transiciones de estado sin requerir entrada para ser procesada. La clase de máquinas nodeterminísticas que utilizan transiciones lambda se denota por NFA-λ . λ Las transiciones lambda representan otro paso para realizar computaciones efectivas de un DFA.Proporcionan también una herramienta útil para el diseño de máquinas que acepten lenguajes complejos. Definición (NFA-λ = Nondeterministic Finite Automaton-λ). λ λ Es una quíntupla M = (Q, S, δ, qo, F ), donde: Q, S, qo, F son iguales que en un NFA. Q = conjunto finito de estados, S = alfabeto (conjunto finito), F ⊆ Q (estados finales o estados de aceptación),qo e Q estado distintivo (inicio), δ = función de transición que va de Q x (S U { λ }) hacia P( Q ).

La definición de detención debe extenderse para incluir la posibilidadde que una computación puede continuar utilizando transiciones lambda después de que la cadena ha sido procesada por completo. Empleando el criterio de aceptación utilizado enun NFA, se acepta la entrada si existe una computación que procese la cadena completa y se detenga en un estado de aceptación. El lenguaje de un NFA-λ se denota por L ( M ). λ Enel diagrama de estados, las transiciones lambda se representan mediante arcos etiquetados con lambda. Las transiciones lambda se pueden usar para construir máquinas complejas apartir de simples.

Lema (NFA-λ Equivalente). λ Sea una quíntupla M = ( Q, S, δ, qo, F ) un NFAλ , ⇒ existe un NFA-λ equivalente M´ = ( Q U λ {q´o, qf }, S, δ´, q´o, {qf } )que satisface las siguientes condiciones: El grado de entrada del estado inicial q´o es cero. El único estado de aceptación de M´ es qf. El grado de salida de qf es cero.