AUTOMATAS FINITOS

1.Sistema de Estados Finitos

2.Definicion Formal de A.F

3.Lenguaje Reconocido por un A.F

4.Representacion de la A.F

5. Diagrama de Moore

1. SISTEMAS DE ESTADOS FINITOS

El autómata finito es un modelo de un sistema, con entradas y salidas discretas. El sistema pude estar en cualquiera de un número finito de configuraciones o "estados". El estado del sistema resume la información concerniente a entradas anteriores y que es necesaria para determinar el comportamiento del sistema para entradas posteriores.
      El mecanismo de control de una máquina de refrescos es un buen ejemplo de un sistema de estados finitos. 

2. DEFINICIÓN FORMAL DE AF

Un autómata finito o máquina de estado finito es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce.
Éstos se definen mediante una quíntupla (E, Q, f, q0, F ) donde:

E: alfabeto de entrada.
Q: conjunto de estados; es conjunto finito no vacío.
f: función de transición. f(p,a)=q
q0 : (perteneciente a Q) estado inicial.
F : (perteneciente a Q) conjunto de estados finales o de aceptación

3. LENGUAJE RECONOCIDO POR UN AF

AF como reconocedor de un Lenguaje:

• Cuando un AF transita desde q0 a un estado final en varios movimientos, se ha producido el RECONOCIMIENTO o ACEPTACIÓN de la cadena de entrada.
• Cuando un AF no es capaz de alcanzar un estado final, se dice que el AF NO RECONOCE la cadena de entrada y que ésta NO PERTENECE al lenguaje reconocido por el AF.

Ejemplo:

A partir del autómata, comprobar si reconoce la palabra “aabbaba”.

Imagen

4. REPRESENTACIÓN DE LOS AF

Los autómatas se pueden representar mediante tablas de transición o diagramas de transición.

Tablas de transición:
• Filas encabezadas por los estados( Q )
• Columnas encabezadas por los símbolos de entrada ( E )

Imagen

5. DIAGRAMA DE MOORE