Autómatas Finitos No determinísticos (AFN)

07.11.2012 20:47

 

 

La diferencia es el no determinismo de esta clase de autómatas. Esto se manifiesta en la función de transición que en los AFD significa moverse de un estado a otro bajo un símbolo de entrada. En un AFN la función de transición también contempla lo anterior, pero además contempla otras dos transiciones: moverse de un estado a varios estados bajo una sola entrada o símbolo; y moverse de un estado a otro bajo no entrada o símbolo. Estas tres transiciones se dan como: