Maquina De estados Finitos

Tarea 6: Diferencia de Máquina de estado finito y Autómata.

La máquina de estado finito
es un modelo computacional que
realiza cómputos en forma automática sobre una entrada para producir
unasalida. Este modelo está conformado por un alfabeto, un conjunto
de estados finito, una función de transición, un estado inicial y un conjunto de
estados finales. Su funcionamiento se basa en una función detransición, que
recibe a partir de un estado inicial una cadena de caracteres pertenecientes al
alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata
se desplaza de un estadoa otro, para finalmente detenerse en un estado
final o de aceptación, que representa la salida.
El Autómata se puede representar mediante grafos particulares, también
llamados diagramas de estadosfinitos, de la siguiente manera:
•

•

•

•

Los estados Q se representan como vértices, etiquetados con su nombre en
el interior.
Una transición δ desde un estado a otro, dependiente de un símbolo delalfabeto, se representa mediante una arista dirigida que une a estos
vértices, y que está etiquetada con dicho símbolo.
El estado inicial q0 se caracteriza por tener una arista que llega a él,proveniente de ningún otro vértice.
El o los estados finales F se representan mediante vértices que están
encerrados a su vez por otra circunferencia.

Diferencia de autómatas deterministas y nodeterministas.

Un autómata determinista es un autómata finito que además es un sistema
determinista; es decir, para cada estado q ∈ Q en que se encuentre el
autómata, y con cualquier símbolo a ∈ Σ del alfabetoleído, existe siempre a lo
más una transición posible δ(q,a).
En un AD no pueden darse ninguno de estos dos casos:
•
•

Que existan dos transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
Queexistan transiciones del tipo δ(q, ε), salvo que q sea un estado final, sin
transiciones hacia otros estados.

Un tipo interesante de autómatas deterministas son los llamados acíclicos y un
ejemplo...