matemática Discreta: AUTÓMATA DE ESTADO FINITO

AUTÓMATA DE ESTADO FINITO

Se trata de una maquina de estado finito en la que 0 ={0,1} , es decir un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida.

Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su 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.

En los estados para los que la última salida es 1 se llaman Estados de Aceptación.

DEFINICIÓN FORMAL

Formalmente, un autómata finito es una 5-tupla (Q, Σ, q₀, δ, F) donde:

Q es un conjunto finito de estados.
∑ es un alfabeto finito;
q₀ ϵ Q es el estado inicial;
δ: Q x ∑ → Q es una función de transición;
es un conjunto de estados finales o de aceptación.

Autómata de Estados Finitos (AF): Describen, reconocen y definen a los Lenguajes Regulares.

Modelo Matemático de un sistema con estados y salidas discretas.

Tipos de Autómatas Finitos:

- Autómata Finito Determinista (AFD). No pueden estar en más de un estado simultáneamente.

- Autómata Finito No Determinista (AFN). Puede estar en varios estados al mismo tiempo.

Definición de Autómatas de estados Finitos Deterministas (AFD):

Un AFD es una quíntupla A = (Q, Σ, δ, q0, F)

Por ejemplo: si p y q están en Q y a en Σ,

Se define la transición δ (q,a) = p.

En la figura se observa como hay una transición de q a p dado a.

Es decir, existe un arco etiqueta a entre q u p.

Los estados de aceptación se denotan gráficamente con un doble círculo, y en la tabla de transición con asterisco al lado del estado. Por ejemplo si r esta en F debe ser denotado con doble circulo como se observa en la figura.

Nota: En los AFD debe cumplirse que: Para toda a que esta en Σ existe exactamente una transición de salida de cada estado.

Notación para la Función de Transición: Se tiene tres formas para presentar la función de transición cualquiera de ellas es suficiente para completar el diseño del AFD. Estas son:

a) Diagrama de Transición

b) Función de transición

c) Tabla de Transiciones: Representación Tabular

Ejemplo: Dado el lenguaje L = {x | x en {0,1} y x comienza con 0}, es decir todas las cadenas binarias que comienzan con 0. El AFD que lo reconoce es el siguiente:

M = (Q, Σ, δ, q0, F)

Σ= {0,1}, F = {q1}, Q= {q0, q1, q2}

δ	0	1
--> q0	q1	q2
*q1	q1	q1
q2	q2	q2

Función de transición δ

δ(q0,0) = q1

δ(q0,1) = q2

δ(q1,0) = q1

δ(q1,1) = q1

δ(q2,0) = q2

δ(q2,1) = q2

Las tres representaciones de la función de transición son equivalentes, y cada suficiente para dar el AF. Puede escoger una representación pero comprendiendo la relación entre ellas.

Autómata Finito No Determinista AFND.

Son autómatas de estados finitos que tienen la capacidad de estar en más de un estado simultáneamente. Ventaja: son más compactos, flexibles y fáciles de diseñar que los AFD permiten cero, una o más transiciones de salida de un estado para el mismo símbolo. No hay que considerar todos los casos en cada estado.

La diferencia con AFD es la función δ: Q x Σ→ 2Q ó también δ: Q x Σ→ Q*

En la figura δ (q,a) = {p, r}

A= (Q, Σ, δ, q0, F)

δ: Q x Σ → Q*

δ (q,a) = R , R Q , δ(q,a) = {p, r}

Función de Transición Extendida:

δˆ = Q x Σ* → Q*

1) δˆ (q,ε) = {q}

2) δˆ (q,xa) = { r | para algún p en δˆ(q,x), δˆ(p,a) = r }

REPRESENTACIÓN COMO DIAGRAMAS DE ESTADOS

Los autómatas finitos se pueden representar mediante grafos particulares, también llamados diagramas de estados finitos, 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 del alfabeto, se representa mediante una arista dirigida que une a estos vértices, y que está etiquetada con dicho símbolo.
El estado inicial q₀ 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.

Ejemplo

Su definición sobre el alfabeto Σ={0,1}, posee dos estados s1 y s2.
Sus transiciones son δ(s1,0)=s2, δ(s1,1)=s1, δ(s2,0)=s1 y δ(s2,1)=s2.
Su estado inicial es s1, que es también su único estado final

Ejemplo:

1 1) Dibuje un diagrama de transmisión para la M.E.F, definida por la tabla siguiente y determine que es un autómata de estado finito. Indique el conjunto de los estados de aceptación: