Automatas Finitos

Índice
I. Definición ………………………………………..……………. 2
II. Diagramas de Transición ……………………………….…... 3
III. Autómatas Finitos Determinísticos ………………………… 4
III.1 Definición ………………………………….…………….. 5
III.2 Interpretación de funcionamiento ………………….….. 6
III.3 Extensión a palabras …………………………………… 6
III.4 Aceptación de palabras ………………………………... 7
III.5 Lenguaje reconocido por un AFD …………………….. 8III.6 Accesibilidad entre estados …………………………… 9
III.7 Conjunto Conexo ……………………………………….. 9
III.8 Equivalencias en los AFD …………………..…………..10
III.9 Conjunto cociente ………………………………..………11
III.10 Minimización de AFD ………………..…………………14
IV. Autómatas Finitos No Determinísticos …………………. . 23
IV.1 Gramáticas …………………………………………….. 25
V. Equivalencias entre expresiones regulares y AFD ………31
VI.Bibliografía ………………………………………………….. 36
VII. Linkografía ………………………………………………….. 36

AUTÓMATAS FINITOS
I.DEFINICIÓN:
Un autómata finito (AF) o máquina de estado finito es 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 dichosestados.

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.

Consiste en un conjunto finito de estados y unconjunto de transiciones entre esos estados, que dependen de los símbolos de la cadena de entrada. El autómata finito acepta una cadena x si la secuencia de transiciones correspondientes a los símbolos de x conduce desde el estado inicial a un estado final.

Un autómata finito es capaz de reconocer un conjunto regular, es decir, un conjunto de cadenas denotado por cualquier expresión regular.Recordemos que una expresión regular denota a un lenguaje regular.
Un autómata finito es un reconocedor para un lenguaje, su programación no es una tarea compleja, su entrada es una cadena x y responde “si” si x es una sentencia del lenguaje, “no” de otra manera.

II.DIAGRAMAS DE TRANSICIÓN
También llamado diagrama de estados o red de transiciones, es una representación gráfica delautómata, y está compuestos de:

Círculos.- Es un conjunto finito, que van a representar posiciones o estados. Cada uno de ellos lo podremos etiquetar con un número (un nombre) para identificarlo posteriormente. A Uno de ellos se le apunta con una flecha (apuntador) para denotar que se trata del estado inicial. A Uno o más de ellos son círculos dobles van a ser el/los estados de aceptación,designando así estados en los que se reconoce la cadena como válida. Al estado actual puede ser a la vez de aceptación, aunque no es obligatorio
Arcos.- Es cada una de las flechas que unen dos estados cualesquiera. Cada arco estará etiquetado con el símbolo o el tipo de símbolo que podría presentarse en la cadena de entrada que se analice.

Decimos que el autómata representado por un diagrama detransiciones acepta una cadena si la secuencia de símbolos que aparecen en la misma (de izquierda a derecha) corresponde a una secuencia de arcos rotulados que conducen del círculo con apuntador a un círculo doble.

A partir del diagrama de transiciones se puede hacer un programa que reconozca estructuras léxicas (cadenas válidas), aunque el resultado de la conversión no sea la mejor de lasposibles soluciones.

Se designa una variable para almacenar el estado actual y se inicializa como el estado inicial. Con una dentro de una sentencia WHILE (no sea fin de cadena), una sentencia CASE OF dirige las transiciones a otros estados, dando el estado siguiente mediante IF-THEN-ELSE anidados, dependiendo del símbolo leído. Si la cadena es inaceptable, el programa sale a una rutina de error....