Autómatas

Autómata finito determinista. Tabla y diagrama transición. Estado accesible. Conexos. Minimación AF. Equivalencia estados. Equivalentes. Determinista

  • Enviado por: Miguel Amado Fernadez goriña
  • Idioma: castellano
  • País: España España
  • 15 páginas
publicidad

Autómatas Finitos

Autómatas Finitos Deterministas

Se llama Autómata Finito Determinista (AFD) a la quíntupla:

(", Q, f, q0, F)

  • " es un alfabeto, llamado “alfabeto de entrada”.

  • Q es un conjunto finito, no vacío llamado “conjunto de estados”.

  • f es una función f: Qx" ! Q que se llama “función de transición”.

  • q0"Q es el “estado inicial”.

  • F"Q es el conjunto de “estados finales”, o “estados de aceptación”, no vacío.

Un AFD puede considerarse como una máquina secuencial de Moore, cuyo alfabeto de entrada sea ", su alfabeto de salida "S={0,1}, y donde F será el conjunto de los estados tales que g(q)=1.

Tabla de Transición


Será una tabla cuyas filas están encabezadas por los estados (elemen-tos de Q). Los encabezamientos de las columnas son los símbolos del alfabeto de entrada (los elementos de "). Cumpliéndose que el elemento i, j de la tabla de transición corresponde al valor de f(qi, ej), donde qi es el elemento i-ésimo de Q, y ej es el elemento j-ésimo de ". Tanto el estado inicial como el final estarán marcados por ! y por * respectivamente. Nota: el estado final puede ser indicado también rodeando el estado por un círculo.

("): a1...an

!q0

.....

qi

......

*qf

Ejemplo:

AF=({0,1},{q0,q1,q2}, f, q0, {q1} )

f

0

1

!q0

q1

q0

*q1

q0

q2

q2

q1

-


Diagrama de Transición

Es un grafo dirigido que se forma de la siguiente manera:

El grafo tendrá tantos nodos como |Q|, cada nodo estará etiquetado por un elemento de Q.

Si f(qi, ej) = qk, dibujaremos una rama dirigida desde el nodo de etiqueta qi hasta el nodo de etiqueta qk. La etqueta de la rma será ej.

El estado inicial estará señalado mediante el símbolo !.

Los estados finales estarán señalados mediante el simbolo *, o doble círculo alrededor de la etiqueta del estado final.

Representamos los estados como: