Automatas de Estado Finito

Contenido

Conocer el concepto de los autómatas finitos
Conocer los tipos de autómatas finitos DFA y DNFA.
Funcionamiento de los autómatas finitos DFA
Funcionamiento de los autómatas finitos DNFA.
Ejemplos de autómatas finitos usando JFLAP

conceptos previos

Antes de crear los ejemplos mostrados debes haber leído la entrada sobre JFLAP, de manera de tener la respuesta para las siguientes preguntas.

¿Qué es JFlap, como se instala y para qué se usa?
¿Qué es JLex, cómo se instala y para qué se usa?
¿Cómo implementar problemas de lenguajes formales según la jerarquía de Chomsky, con Jflap?
Qué son los autómatas finitos y autómatas de pila.

¿Qué es un autómata Finito?

Un autómata finito es un conjunto de nodos y aristas que representan trayectorias para generar una expresión bajo un alfabeto.

Undiagramadetransiciónesunautómata finito.

Automatas de estado finito from Pedro Antonio Villalta

Elementos del Autómata Finito

Los estados se identifican dentro de un circulo.
El estado inicial recibe una flecha de transición que llega de ninguna parte.
Los estado aceptadores pueden identificarse con doble circulo o con una cruz(igual que signo +) al lado de ellos.
Las posibles transiciones se indicaran con flechas que van de un estado a otro, o incluso a sí mismos. Deben etiquetarse con el símbolo que produce el cambio de estado.

Los Estado del Autómata

Entonces decimos que los estado del autómata pueden ser:
Estados iniciales
Estados finales llamados aceptadores
Estados finales no aceptadores
La palabra que va de un estado a otro solo pertenece al lenguaje si el estado que la recibe es aceptador.
Y lo contrario, si llega al final hasta un estado no aceptador, la palabra no pertenece al lenguaje.

EJEMPLO DE Autómata Finito

Supongamos que tenemos el siguiente ejemplo:

El lenguaje X es capaz de identificar la siguiente cadena.

w = aabab

Tratemos de identificar los procesos del Autómata.

Explicación del autómata:

1. Para comenzar estamos en el estado A, podemos llamarle estado 1.

2. Hacemos la transición a B cuando leemos el símbolo a.

3. Realizamos la siguiente transición de B hacia B porque leemos nuevamente otro símbolo a.

4. Para leer b creamos otro estado D al que llegaremos desde donde estamos que es B.

5. Para leer el siguiente símbolo que es a transferimos de nuevo hacia B.

6. Luego para leer el siguiente símbolo b, el autómata regresa hasta D.

Representación de autómatas finitos con algorítmos

CLASIFICACIÓN DE LOS AutómataS FinitoS

Autómatas finitos determinísticos (DFA)

· Es un dispositivo que puede estar en un estado de entre un número finito de los mismos; uno de ellos será el estado inicial y por lo menos uno será estado de aceptación.

· Tiene un flujo de entrada por el cual llegan los símbolos de una cadena que pertenecen a un alfabeto determinado.

· Se detecta el símbolo y dependiendo de este y del estado en que se encuentre hará una transición a otro estado o permanece en el mismo.

· El mecanismo de control o programa es que determina cual es la transición a realizar.

Ejemplo Autómatas finitos determinísticos (DFA)

Porqué se les llama autómatas finitos y porqué determinístico

Porqué finito:

Se refiere que hay un conjunto finito de estados.

Porque determinista:

La palabra determinista es porque el programa no debe tener ambigüedades, es decir, en cada estado solo se puede dar una y solo una (ni dos ni ninguna) transición para cada símbolo posible.

El autómata acepta la cadena de entrada si la máquina cambia a un estado de aceptación después de leer el último símbolo de la cadena.

Si después del último símbolo la máquina no queda en estado de aceptación, se ha rechazado la cadena.

Tuplas de autómatas finitos

El diagrama determinista estará caracterizado porque debe estar totalmente definido:

Para cada estado solo debe salir un arco y solo uno para cada símbolo (el autómata no puede determinar la transición en el caso de que haya dos arcos con el mismo símbolo o no haya ninguno).

Simbología de los autómatas finitos