Maquinas De Estado Finito

Objetivo.

Con este trabajo se pretende definir es ciertos aspectos el tema de máquinas de estado finito, los aspectos a definir son su significado, los elementos, sus funcionamientos, sus características y finalmente los usos y aplicaciones que encontramos en la vida diaria, las imágenes plasmadas en el trabajo serán para comprender como funcionan las máquinas de esto finito gráficamente.

Introducción.

El origen de los autómatas finitos probablemente se remonta a su uso implícito en máquinas electromecánicas, desde principios del siglo XX. Ya en 1907, el matemático ruso Andréi Márkov formalizó un proceso llamado cadena de Markov, donde la ocurrencia de cada evento depende con una cierta probabilidad del evento anterior. Esta capacidad de "recordar" es utilizada posteriormente por los autómatas finitos, que poseen una memoria primitiva similar, en que la activación de un estado también depende del estado anterior, así como del símbolo o palabra presente en la función de transición. Este fue el comienzo de los usos de los autómatas finitos, ahora continuaremos detallando su significado y características. 

Máquinas de estado finito.

Es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida.

Elementos.

Este modelo está conformado por:

• Un alfabeto.

• Un conjunto de estados finitos.

• Una función de transición.

• Un estado inicial.

• Un conjunto de estados finales.

Funcionamiento.

Se basa en una función de transició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 estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida.

Características.

Formalmente, un autómata finito es una 5-tupla donde:

• Q: Es un conjunto finito de estados.

• Σ: Es un alfabeto finito.

• q0: Es el estado inicial.

• δ: Es una función de transición.

• F: Es un conjunto de estados finales o de aceptación.

Tipos de máquinas.

Autómata finito 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 alfabeto leído, existe siempre a lo más una transición posible δ(q,a).

En un AFD no pueden darse ninguno de estos dos casos:

• Que existan dos transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;

• Que existan transiciones del tipo δ(q, ε), salvo que q sea un estado final, sin transiciones hacia otros estados.

Autómata finito no determinista.

Es aquel que, a diferencia de los autómatas finitos deterministas, posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.

Haciendo

...