Unidad III

Capítulo

3

Autómatas Finitos

Los autómatas finitos reconocen el lenguaje regular (tipo 3).
Podemos construir un diagrama que nos ayude a determinar los distintos miembros del lenguaje.
Taldiagrama tiene la forma de un grafo dirigido con información adicional añadida, y se llama
diagrama de transición. Los nodos del grafo se llaman estados y se usan para señalar, en ese
momento, hasta quélugar se ha analizado la cadena. Las aristas del grafo se etiquetan con
caracteres del alfabeto y se llaman transiciones. Si el siguiente carácter a reconocer concuerda con
la etiqueta de algunatransición que parta del estado actual, nos desplazamos al estado al que nos
lleve la arista correspondiente. Naturalmente, nosotros debemos comenzar por un estado inicial, y
cuando se hayan tratado todos loscaracteres de la cadena correspondiente, necesitamos saber si la
cadena es “legal”. Para ello se marcan ciertos estados como estados de aceptación o estados finales.
Si cuando ha sido tratada la cadenaen su totalidad terminamos en un estado de aceptación, entonces
la cadena es “legal”. Marcaremos el estado inicial con una flecha () y alrededor de los estados de
aceptación trazaremos un círculo.Por ejemplo el siguiente diagrama, acepta todas las cadenas que están formadas por 0 o más a´s, seguidas por
una única b.

a

b

qo

q1
a,b
q2
a,b

Ejercicio:
1. Considere el lenguaje A={(ab)i | i >=1}, el cual está representado por la expresión regular (ab)+.
Obsérvese que una cadena de este lenguaje ha de tener al menos una copia de ab. Por tanto si se
construye un diagrama de transición paraeste lenguaje, el estado inicial no puede ser también
estado de aceptación..
a,b

b

b
a

a

b
a

18

Obsérvese que se tiene un único estado de aceptación. Si el análisis termina en cualquier otroestado, la cadena no está correctamente construida. Obsérvese, también, que se identifica un prefijo
incorrecto, se realiza un desplazamiento a un estado que no es de aceptación y se permanece en el...