Autómatas Finitos Determinísticos (AFD)
08.11.2012 02:38
Autómatas Finítos Determinísticos (AFD)
Un AFD es un quintuple M = (Q, S, d, q0, F), donde Q es una máquina de estados finíta, S es el alfabeto, q0 es el estado inicial, F es el estado(s) final(es) y d es una función de Q x S a Q llamada la función de transición.
Diagramas de Estado
El diagrama de estado de un AFD es un grafo dirigido-etiquetado
en el cual los nodos representan los estados de la máquina y los
arcos son obtenidos de la función de transición.
Otra definición es la siguiente:
El diagrama de estado de un AFD M = (Q, S, d, q0, F) es un
grafo etiquetado G definido por las sig. condiciones:
i)Los nodos de G son los elementos de Q.
ii)Las etiquetas sobre los arcos de G son elementos de S.
iii)q0 es el nodo inicial, representado con >0
iv)F es el conjunto de nodos aceptadores; cada nodo acaptador
se representa con dos circulos uno dentro de otro.