La palabra autmata evoca algo que pretende imitar las
funciones propias de los seres vivos, especialmente
relacionadas con el movimiento, por ejemplo el tpico robot
antropomorfo. En el campo de los Traductores,
Procesadores, Compiladores e Intrpretes, lo fundamental
no es la simulacin del movimiento, sino la simulacin de
procesos para tratar informacin.
La informacin se codifica en cadenas de smbolos, y un
autmata es un dispositivo que manipula cadenas de
smbolos que se le presentan a su entrada, produciendo
otras tiras o cadenas de smbolos a su salida.
El autmata recibe los smbolos de entrada, uno detrs de
otro, es decir secuencialmente. El smbolo de salida que en
un instante determinado produce un autmata, no slo
depende del ltimo smbolo recibido a la entrada, sino de
toda la secuencia o cadena, que ha recibido hasta ese
instante.
Todo lo anterior conduce a definir un concepto fundamental:
estado de un autmata.
El estado de un autmata es toda la informacin necesaria en un
momento dado, para poder deducir, dado un smbolo de entrada en
ese momento, cual ser el smbolo de salida. Es decir, conocer el
estado de un autmata, es lo mismo que conocer toda la historia de
smbolos de entrada, as como el estado inicial, estado en que se
encontraba el autmata al recibir el primero de los smbolos de
entrada.
El autmata tendr un determinado nmero de estados (pudiendo
ser infinitos), y se encontrar en uno u otro segn sea la historia de
smbolos que le han llegado.
Se define configuracin de un autmata a su situacin en un
instante. Se define movimiento de un autmata como el transito
entre dos configuraciones. Si un autmata se encuentra en un
estado determinado, recibe un smbolo tambin determinado,
producir un smbolo de salida y efectuar un cambio o transicin a
otro estado (tambin puede quedarse en el mismo estado).
El campo de estudio de los Traductores, Procesadores e
Intrpretes son los lenguajes y las gramticas que los
generan. Los elementos del lenguaje son sentencias,
palabras, etc... Formadas a partir de un alfabeto o
vocabulario, que no es otra cosa que un conjunto finito
de smbolos. Establecidas las reglas gramaticales, una
cadena de smbolos pertenecer al correspondiente
lenguaje si tal cadena se ha formado obedeciendo esas
reglas. Entonces un autmata reconocedor de ese
lenguaje, funciona de tal forma que cuando reciba a su
entrada una determinada cadena de smbolos indica si
dicha cadena pertenece o no al lenguaje. Tambin se
mostrar como existe un tipo de autmata para
reconocer cada uno de los tipos de lenguajes
generados por las correspondientes gramticas.
Analizador lxico
AUTMATA FINITO
Para comprender el significado de Autmata Finito, tendremos en
cuenta el trmino mquina, que evoca algo hecho en metal,
usualmente ruidoso y grasoso, que ejecuta tareas repetitivas que
requieren de mucha fuerza o velocidad o precisin.
Ejemplos de estas mquinas son las embotelladoras automticas de
refrescos. Su diseo requiere de conocimientos en mecnica,
resistencia de materiales, y hasta dinmica de fluidos. Al disear tal
mquina, el plano en que se le dibuja hace abstraccin de algunos
detalles presentes en la mquina real, tales como el color con que
se pinta, o las imperfecciones en la soldadura.
El plano de diseo mecnico de una mquina es una abstraccin de
sta, que es til para representar su forma fsica. Sin embargo, hay
otro enfoque con que se puede modelar la mquina embotelladora:
cmo funciona, en el sentido de saber qu secuencia de
operaciones ejecuta. As, la parte que introduce el lquido pasa por
un ciclo repetitivo en que primero introduce un tubo en la botella,
luego descarga el lquido, y finalmente sale el tubo para permitir la
colocacin de la cpsula (corcholata). El orden en que se efecta
este ciclo es crucial, pues si se descarga el lquido antes de haber
introducido el tubo en la botella, el resultado no ser satisfactorio.
Las mquinas que se estudian son abstracciones
matemticas que capturan solamente el aspecto
referente a las secuencias de eventos que
ocurren, sin tomar en cuenta ni la forma de la
mquina ni sus dimensiones, ni tampoco si
efecta movimientos rectos o curvos, etc.
En esta parte se estudian las mquinas abstractas
ms simples, los autmatas finitos, las cuales
estn en relacin con los lenguajes regulares,
como veremos a continuacin.
Al describir una mquina de estados finitos en
particular, debemos incluir las informaciones
que varan de un autmata a otro; es decir, no
tiene sentido incluir descripciones generales
aplicables
a
todo
autmata.
Estas
informaciones son exactamente las que
aparecen en un diagrama de estados y
transiciones, como se presenta ms adelante.
Autmata finito
Un autmata finito es un modelo matemtico de una
mquina que acepta cadenas de un lenguaje definido sobre un
alfabeto.
Consiste en un conjunto finito de estados y un conjunto de
transiciones entre esos estados, que dependen de los smbolos
de la cadena de entrada.
El
autmata finito acepta una cadena x si la secuencia de
transiciones correspondientes a los smbolos de x conduce desde el
estado inicial a un estado final.
Desde el punto de vista intuitivo, podemos ver un autmata
finito como una caja negra de control, que va leyendo
smbolos de una cadena escrita en una cinta, que se puede
considerar ilimitada por la derecha. Existe una cabeza de
lectura que en cada momento est situada en una casilla de
la cinta. Inicialmente, esta se sita en la casilla de ms a la
izquierda. El autmata en cada momento est en uno de los
estado de Q. Inicialmente se encuentra en q0.
En cada paso, el autmata lee un smbolo y segn el estado
en que se encuentre, cambia de estado y pasa a leer el
siguiente smbolo. As sucesivamente hasta que termine de
leer todos los smbolos de la cadena. Si en ese momento la
mquina est en un estado final, se dice que el autmata
acepta la cadena. Si no est en un estado final, la rechaza.
Ejemplo de autmata finito: Se va a disear un autmata que
reconozca el paso de un alumno por un curso, por ejemplo,
Autmatas y lenguajes formales.
Representar las distintas decisiones que se realizan y si se aprueba
o aplaza el curso. Se controla que no haya ms de dos
convocatorias por ao y se termina cuando se aprueba el curso.
Habr un alfabeto de entrada contendr los siguientes elementos:
P: El alumno se presenta al examen.
N: El alumno no se presenta al examen.
A: El alumno aprueba el examen.
S: El alumno aplaza un examen.
Comienza en un estado, Inicio. A continuacin decide si
presenta en Febrero o no. Si no presenta y aprueba,
termina. Si no presenta o aplaza, se decide si se presenta
en septiembre, pero como hay que controlar que un
estudiante no se presente a tres convocatorias en un ao,
los estados son distintos en ambos casos. Si en septiembre
aprueba, termina. Si suspende o aplaza y ya se haba
presentado en febrero, comienza de nuevo. En otro caso,
puede decidir si presenta en diciembre. Si aprueba, termina
y si suspende, empieza de nuevo.
Este esquema corresponde a un autmata finito. Se
caracteriza por una estructura de control que depende de
un conjunto finito de estados. Se pasa de unos a otros
leyendo smbolos del alfabeto de entrada. Este autmata
representa una versin simplificada del problema real, ya
que no controla el nmero total de convocatorias. Un
autmata para todos los cursos se puede construir uniendo
autmatas para cada una de los cursos, pero teniendo en
cuenta relaciones como requisitos entre los mismos.
Ejemplo
La maquina de refresco:
Caractersticas:
El refresco vale S/1.00
Solo Acepta monedas de S/1.00, S/0.50, S/0.25
La maquina no da vuelto
Ejemplo:
Supongamos que se quiere modelar el siguiente
comportamiento de un horno microondas:
El horno microondas posee una puerta.
Si la puerta est cerrada, entonces puede estar o no
en funcionamiento (segn se prenda o apague).
Estando prendido no es posible abrir la puerta del
horno sin antes apagarlo.
Tambin asumamos lo siguiente: en cualquier
momento es posible establecer el modo de coccin.
No es obligatorio etiquetar los nodos, sin embargo
puede resultar muy til hacerlo: sobre todo aquellos
nodos que representan los estados principales de que
se est modelando.
Ejemplo
La mquina del ejemplo anterior
se representa con una tabla
O bien se representa con un
diagrama
Autmata finito determinista
Podemos usar un diagrama de transicin para ayudar a determinar si una
cadena pertenece o no a un lenguaje.
Los nodos del diagrama se denominan estados y se utilizan para sealar hasta
donde se ha analizado la cadena.
Las aristas se denominan transiciones y se etiquetan con los smbolos del
alfabeto.
Existe un estado, llamado estado inicial, que es de donde parte el anlisis de
toda cadena.
Algunos estados se marcan como estados de aceptacin para determinar si
una cadena es legal o no.
La cadena es legal si se termina su anlisis en un estado de aceptacin.
Los estados de aceptacin se representan encerrados en un crculo.
Diagramas de Estado
El diagrama de estado de un AFD es un grafo dirigido-etiquetado
en el cual los nodos representan los estados de la mquina y los
arcos son obtenidos de la funcin de transicin.
Otra definicin es la siguiente:
El diagrama de estado de un AFD M = (Q, S, d, q0, F) es un
grafo etiquetado G definido por las sig. condiciones:
i) Los nodos de G son los elementos de Q.
ii) Las etiquetas sobre los arcos de G son elementos de S.
iii) q0 es el nodo inicial, representado con >
iv) F es el conjunto de nodos aceptadores; cada nodo acaptador
se representa con
Construccin de diagramas de
transicin
Para construir un diagrama de transiciones a partir de una
descripcin de un autmata, se procede como sigue.
Se dibujan nodos para cada estado del autmata, luego se
trazan flechas desde cada estado qi hacia el qj etiquetndolas
con el smbolo de entrada correspondiente, se marca el estado
inicial y los estados de aceptacin.
Autmata determinstico
A = ({q0, q1, q2}, {a, b}, , q0, {q0, q1})
(q0, a)= q0
(q0, b)= q1
(q1, a)= q2
(q1, b)= q1
(q2, a)= q2
(q2, b)= q2
Ejemplo
Solucin:
Se construye el diagrama de estados, colocando en
primer lugar todos los estados dentro de crculos,
marcando con doble crculo el estado final. El estado
inicial se indica con una flecha que lo seala con la
palabra INICIO encima. Para construir las ramas, nos
situamos en el primer estado de la tabla de transiciones
y se observa que f(q1,a)=q2, entonces se traza una
flecha entre q1 y q2, apuntando a q2, y se coloca
encima de la flecha el smbolo del vocabulario de
entrada a. De igual forma se recorre la tabla de
transiciones para cada estado y entrada completndose
el diagrama de Moore.
Teora computacional
Clase 08: Autmatas finitos
Prof. Edgardo Adrin Franco Martnez
Lenguaje reconocido por un autmata finito
Los identificadores de C son cadenas de letras, dgitos y
guiones bajos.
letra_
dgito
id
[A-Za- z_]
[0-9]
letra_ ( letra_ |
dgito)*
Teora computacional
Clase 08: Autmatas finitos
Prof. Edgardo Adrin Franco Martnez
Ejemplo
Solucin : Este ejemplo es inverso al anterior, pues se da un
lenguaje y se pide el autmata que lo reconoce. En primer lugar
se construye un diagrama de Moore, de tal forma que a partir
del estado inicial, despus de leer una letra, acepte letras o
dgitos de forma variable, y cuando encuentre un carcter
diferente de letra o dgito alcance el estado final. El diagrama de
Moore es el que se muestra en la figura.
El autmata finito se deduce del diagrama de estados y
es el siguiente:
donde f se define por :
Teora computacional
Clase 08: Autmatas finitos
Prof. Edgardo Adrin Franco Martnez
$ representa a el fin de la cadena
Ejemplo:
Considrese
el
determinstico
siguiente
autmata
M = (Q,,,q0,F), donde
Q = {qo,q1}
= {a, b}
qo = estado inicial
F = { qo }
y es la funcin tabulada a continuacin:
finito
Entonces su diagrama de transicin (diagrama de
estados) correspondiente es:
Claramente se puede llegar a la conclusin de
L(M) es el conjunto de todas las cadenas que
tienen un nmero par de bs
Si el autmata M recibe como entrada la cadena
aabba, su configuracin inicial sera (q0,aabba)
Entonces:
Por lo tanto aabba es aceptada por el
autmata M
AUTMATAS FINITOS Y EXPRESIONES
REGULARES
Ejemplo:
Considrense las siguientes reglas de
produccin para una gramtica que genera las
mismas cadenas que la expresin regular
anterior.
S es el smbolo inicial.
S genera una A, seguida de una B y
finalmente una C.
A genera solamente una a.
B genera una b seguida de una B genera
la cadena vaca (ningn carcter).
C genera una c.
Las letras maysculas representan la parte de la
cadena final que an no ha sido sustituida por su
correspondiente lado derecho.
Claramente, la gramtica anterior genera las
cadenas {ac, abc, abbc, abbbc, abbbbc, ......}
1) ab*baa*
q0
2) xyz(zy)*
q0
Expresiones regulares
b
a
q1
q1
q2
q2
3) 01(10)*
q0
q1
q2
q3
z
q3
q2
y
q3
AFD
q0
q1
q2
q0
q1
q2
q1
q2
q2
AFND
a
q0
estados
q1
q2
Es un autmata finito no determinstico ya que
posee ms de un estado en una celda.
estados
q0
q0 q1
q2
q1
q2
q2
Proceso computacional
Es el proceso que se lleva a cabo cuando a un autmata se le
entrega una palabra.
Sirve para llegar a un estado de aceptacin o de rechazo.
Para que una palabra sea aceptada debe de ocurrir dos
cosas:
Cond1) La palabra debe de terminarse o agotarse (esto es,
que no quede ninguna letra sin procesar).
Cond2) El estado que queda al finalizar debe ser estado de
aceptacin.
Ejemplo: Reconocer 10101
Proceso computacional para 10101
w = 10101
Formalizado:
L = {{0,1}, {q0, q1}, d, q0, {q0}}
Funcin de transicin del AFD:
(definida por tabla)
d 0
q0 q1
q1 q0
1
q0
q1
Ejemplo: Reconocer 10101
Revisamos la definicin del AF,
buscando el estado inicial.
Proceso computacional para 10101
w = 10101
Formalizado:
L = {{0,1}, {q0, q1}, d, q0, {q0}}
Funcin de transicin del AFD:
(definida por tabla)
d 0
q0 q1
q1 q0
1
q0
q1
Ejemplo: Reconocer 10101
Estado inicial: q0. Lo pondremos como
estado actual.
Proceso computacional para 10101
w = 10101
Formalizado:
L = {{0,1}, {q0, q1}, d, q0, {q0}}
Funcin de transicin del AFD:
(definida por tabla)
d 0
q0 q1
q1 q0
1
q0
q1
Estado actual: q0
Letra actual:
Ejemplo: Reconocer 10101
Ahora pondremos la primera letra como
la letra actual
Proceso computacional para 10101
w = 10101
Formalizado:
L = {{0,1}, {q0, q1}, d, q0, {q0}}
Funcin de transicin del AFD:
(definida por tabla)
d 0
q0 q1
q1 q0
1
q0
q1
Estado actual: q0
Letra actual: 1
Ejemplo: Reconocer 10101
Inicia el proceso. Buscamos en la tabla el
estado siguiente para el estado y la letra
actual.
Proceso computacional para 10101
w = 10101
Formalizado:
L = {{0,1}, {q0, q1}, d, q0, {q0}}
Funcin de transicin del AFD:
(definida por tabla)
d 0
q0 q1
q1 q0
1
q0
q1
Estado actual: q0
d(q0, 1) = q0
Letra actual: 1
Ejemplo: Reconocer 10101
Ponemos el nuevo estado encontrado como
estado actual.
Proceso computacional para 10101
w = 10101
Formalizado:
L = {{0,1}, {q0, q1}, d, q0, {q0}}
Funcin de transicin del AFD:
(definida por tabla)
d 0
q0 q1
q1 q0
1
q0
q1
Estado actual: q0
d(q0, 1) = q0
Letra actual: 1
Ejemplo: Reconocer 10101
Avanzamos una letra de la palabra y la
colocamos como letra actual
Proceso computacional para 10101
w = 10101
Formalizado:
L = {{0,1}, {q0, q1}, d, q0, {q0}}
Funcin de transicin del AFD:
(definida por tabla)
d 0
q0 q1
q1 q0
1
q0
q1
Estado actual: q0
d(q0, 1) = q0
Letra actual: 0
Ejemplo: Reconocer 10101
Ahora buscamos el nuevo estado siguiente
para el nuevo estado y letra actual.
Proceso computacional para 10101
w = 10101
Formalizado:
L = {{0,1}, {q0, q1}, d, q0, {q0}}
Funcin de transicin del AFD:
(definida por tabla)
d 0
q0 q1
q1 q0
1
q0
q1
Estado actual: q0
d(q0, 1) = q0
d(q0, 0) = q1
Letra actual: 0
Ejemplo: Reconocer 10101
Colocamos el nuevo estado como actual y
avanzamos una letra
Proceso computacional para 10101
w = 10101
Formalizado:
L = {{0,1}, {q0, q1}, d, q0, {q0}}
Funcin de transicin del AFD:
(definida por tabla)
d 0
q0 q1
q1 q0
1
q0
q1
Estado actual: q1
d(q0, 1) = q0
d(q0, 0) = q1
Letra actual: 1
Ejemplo: Reconocer 10101
Busquemos ahora un estado siguiente para la
combinacin de estado/letra actual
Proceso computacional para 10101
w = 10101
Formalizado:
L = {{0,1}, {q0, q1}, d, q0, {q0}}
Funcin de transicin del AFD:
(definida por tabla)
d 0
q0 q1
q1 q0
1
q0
q1
Estado actual: q1
d(q0, 1) = q0
d(q0, 0) = q1
d(q1, 1) = q1
Letra actual: 1
Ejemplo: Reconocer 10101
Colocamos el nuevo estado como estado
actual y avanzamos una letra
Proceso computacional para 10101
w = 10101
Formalizado:
L = {{0,1}, {q0, q1}, d, q0, {q0}}
Funcin de transicin del AFD:
(definida por tabla)
d 0
q0 q1
q1 q0
1
q0
q1
Estado actual: q1
d(q0, 1) = q0
d(q0, 0) = q1
d(q1, 1) = q1
Letra actual: 0
Ejemplo: Reconocer 10101
Nuevamente, buscamos un estado siguiente
para la actual combinacion estado/letra actual
Proceso computacional para 10101
w = 10101
Formalizado:
L = {{0,1}, {q0, q1}, d, q0, {q0}}
Funcin de transicin del AFD:
(definida por tabla)
d 0
q0 q1
q1 q0
1
q0
q1
Estado actual: q1
d(q0, 1) = q0
d(q0, 0) = q1
d(q1, 1) = q1
d(q1, 0) = q0
Letra actual: 0
Ejemplo: Reconocer 10101
Colocamos el nuevo estado como actual y
avanzamos una letra
Proceso computacional para 10101
w = 10101
Formalizado:
L = {{0,1}, {q0, q1}, d, q0, {q0}}
Funcin de transicin del AFD:
(definida por tabla)
d 0
q0 q1
q1 q0
1
q0
q1
Estado actual: q0
d(q0, 1) = q0
d(q0, 0) = q1
d(q1, 1) = q1
d(q1, 0) = q0
Letra actual: 1
Ejemplo: Reconocer 10101
Nuevamente, buscamos un estado siguiente
para la combinacin estado/letra actual.
Proceso computacional para 10101
w = 10101
Formalizado:
L = {{0,1}, {q0, q1}, d, q0, {q0}}
Funcin de transicin del AFD:
(definida por tabla)
d 0
q0 q1
q1 q0
1
q0
q1
Estado actual: q0
d(q0, 1) = q0
d(q0, 0) = q1
d(q1, 1) = q1
d(q1, 0) = q0
d(q0, 1) = q0
Letra actual: 1
Ejemplo: Reconocer 10101
Colocamos el estado como actual y
avanzamos una letra
Proceso computacional para 10101
w = 10101
Formalizado:
L = {{0,1}, {q0, q1}, d, q0, {q0}}
Funcin de transicin del AFD:
(definida por tabla)
d 0
q0 q1
q1 q0
1
q0
q1
Estado actual: q0
d(q0, 1) = q0
d(q0, 0) = q1
d(q1, 1) = q1
d(q1, 0) = q0
d(q0, 1) = q0
Letra actual: l
Ejemplo: Reconocer 10101
Pero la palabra ya acab (cond1).
Verifiquemos si el estado al que hemos llegado
es aceptacin (cond2) o rechazo
Proceso computacional para 10101
w = 10101
Formalizado:
L = {{0,1}, {q0, q1}, d, q0, {q0}}
Funcin de transicin del AFD:
(definida por tabla)
d 0
q0 q1
q1 q0
1
q0
q1
Estado actual: q0
d(q0, 1) = q0
d(q0, 0) = q1
d(q1, 1) = q1
d(q1, 0) = q0
d(q1, 1) = q0
Letra actual: l
q0 F?
Ejemplo: Reconocer 10101
Pero la palabra ya acab (cond1).
Verifiquemos si el estado al que hemos llegado
es aceptacin (cond2) o rechazo
Proceso computacional para 10101
w = 10101
Formalizado:
L = {{0,1}, {q0, q1}, d, q0, {q0}}
Funcin de transicin del AFD:
(definida por tabla)
d 0
q0 q1
q1 q0
1
q0
q1
Estado actual: q0
d(q0, 1) = q0
d(q0, 0) = q1
d(q1, 1) = q1
d(q1, 0) = q0
d(q1, 1) = q0
Letra actual: l
q0 F?
Ejemplo: Reconocer 10101
Pero la palabra ya acab (cond1).
Verifiquemos si el estado al que hemos llegado
es aceptacin (cond2) o rechazo
Proceso computacional para 10101
w = 10101
Formalizado:
L = {{0,1}, {q0, q1}, d, q0, {q0}}
Funcin de transicin del AFD:
(definida por tabla)
d 0
q0 q1
q1 q0
1
q0
q1
Estado actual: q0
d(q0, 1) = q0
d(q0, 0) = q1
d(q1, 1) = q1
d(q1, 0) = q0
d(q1, 1) = q0
Letra actual: l
q0 F?
La palabra
10101 es
aceptada.
DIAGRAMAS INCOMPLETOS: ESTADO DE ABSORCIN
Con frecuencia nos encontramos AFDs como el siguiente
Si observamos con un poco de atencin vemos que la transicin (p,1) no
est representada, lo que contradice la definicin de AFD puesto que hemos
afirmado que es una aplicacin. Lo que ocurre en realidad es que la
mquina no ha sido completamente dibujada, por comodidad y claridad.
Debemos entender que todas
las transiciones que falten en el
diagrama de un AFD van a un
nico estado no final, que
llamamos
genricamente
estado de absorcin. As el
diagrama completo de es
El estado s es el estado de absorcin
y con frecuencia desaparece del
grfico del autmata, pero no
debemos olvidar que est ah
aunque no lo dibujemos.
ESTADOS INACCESIBLES
Ejemplo:
En el AFD de la figura, el estado r es
inaccesible por que no se puede alcanzar a
partir del estado inicial
AUTMATA CONEXO
Un AFD decimos que es conexo si no tiene estados
inaccesibles. Si un AFD no es conexo basta eliminar los
estados inaccesibles y todas sus transiciones (las de entrada y
las de salida) para obtener un nuevo AFD conexo equivalente
al de partida.
El AFD obtenido quitando el estado r y sus transiciones, es
conexo
Disear un autmata finito determinstico que acepte
nmeros impares en binario
binario
1
decimal
11
111
101
1001
1011
1101
5
9
11
13
q0
1
1
0
q1
Disear un autmata finito determinstico que acepte todas las palabras sobre
{0,1} que tengan un nmero impar de 1s.
q0
q1
Disear un autmata finito determinstico que acepte todas las palabras sobre
{0,1} que terminan con 01.
q0
q1
0
1
q2
Ejemplo: El siguiente AFD acepta el conjunto de cadenas que
contienen la subcadena bb y donde S={a,b}. Esto quiere decir
que L(M) = (a|b)*bb(a|b)* .
M: Q = {q0, q1, q2 }
S = {a, b}
F = {q2}
La funcin de transicin d es dada en forma tabular y llamada
tabla de transicin.
q0
q1
q2
q0
q1
q2
q2
q0
q2
Para las cadenas abba y abab tenemos las siguientes
operaciones (computaciones) en la tabla:
[q0, abba]
-[q0, bba]
-[q1, ba]
-[q2, a]
-[q2, l]
acepta
[q0, abab]
-[q0, bab]
-[q1, ab]
-[q0, b]
-[q1, l]
rechazado
La cadena abba es aceptada ya que la computacin se para (halts)
en estado q2.
Una cadena de entrada es aceptada si existe una computacin que
procesa toda la cadena de entrada y para en un estado final o
aceptador.
v) Existe un arco desde nodo qi a qj etiquetado a si d(qi,a)=qj.
vi) Por cada nodo qi y smbolo a es miembro de S, existe
exactamente un arco etiquetado a que sale de qi.
Ejemplo: El diagrama de estados para el AFD del ejemplo anterior:
a,b
a
q0
q1
a
q2
El siguiente diagrama acepta
cadenas de la forma (ab)*.
El mismo autmata con estados
etiquetados q0, q1, q2
Estado/Estrada
q0
q1
q2
q1
q2
q2
q2
q0
q2
b
q0
b
a,b
q2
q1
a
Ejemplo
Por ejemplo, el AFD del diagrama anterior se representa mediante M = (S, Q,
s, F, d) donde
b
Q = {q0, q1, q2}
q0
S = {a, b}
F = {q0}
y d se define por la tabla
s = q0
d
q0
q1
q2
q1
a,b
q1
q2
q2
q2
q2
q0
q2
Construir un AFD que acepte el ={0,1} donde las cadenas validas son aquellas
donde los 1s son mltiplos de 3.
0
1
q0
q1
q2
q3
Disear un AFD que acepte el = {0,1} donde las cadenas vlidas son aquellas que
terminan en xx.
y
q0
x
y
q1
q2
Disear un AFD que acepte el = {0,1} donde las cadenas vlidas son aquellas que
terminan en 0101.
q0
q1
q2
0
0
q3
q4
0
Disear un AFD que acepte el siguiente lenguaje regular
0*10*(10*10*)*
0
q0
0
q1
1
1
q3
Ejemplo
Sea el autmata finito A1, donde E={a,b} u {};
Q={q1,q2,q3,q4} y la funcin f viene dada por la
siguiente tabla y el conjunto de estados finales es
f={q3}
f
a
b
q1
q2
q4
q3
q4
q3
q2
q4
q2
q4
q3
q4
Determinar el lenguaje que reconoce, representar el
diagrama de Moore e indicar la expresin regular que
representa al lenguaje.
Solucin: Se construye el diagrama de Moore, colocando
en primer lugar todos los estados dentro del circulo,
marcando con doble circulo el estado final. El estado
inicial se indica con una flecha que lo seala con la
palabra INICIO encima.
Para construir las ramas, nos situamos en el primer
estado de la tabla de transiciones y se observa que:
f(q1,a) =q2
Entonces se traza la flecha q1 y q2, apuntando a q2 y se
coloca encima de la flecha el smbolo del vocabulario de
entrada a. De igual forma se recorre la tabla de
transiciones para cada estado y entrada completndose
el diagrama de moore.
Ejemplo
Sea ={a, b}, Q = {0, 1, 2}, q0 =0, F = {2}, y viene definida as:
Qi/
0
1
2
a
1
2
2
b
0
0
2
Se define el diagrama de transiciones de dicho autmata como
un grafo dirigido, en el que los estados se representan por
nodos, las transiciones por flechas, de tal manera que dicho
grafo satisface la definicin de la funcin de transicin
En este caso el autmata de la funcin sera:
(0, a) = 1, (0, b) = 0, (1, a) = 2,
(1, b)=0, (2, a) = 2, (2, b)=2
Ntese que para todos los smbolos del alfabeto, existe una
transicin de algn estado.
Sabiendo esto, el anterior autmata quedara representado as
Se define un estado de absorcin o muerte como
aquel estado q Q, y qF, que no tiene ninguna
transicin
hacia
ningn
otro
estado
(opcionalmente, a s mismo puede tenerlos),
nicamente hay transiciones que inciden en l. Es
decir:
si (q, a) = , , (q, a) = q, a .
Como vemos, el estado 3 no tiene ninguna transicin, nicamente
hay transiciones que inciden en l. Adems, 3F, luego 3 es un
estado de muerte.
Cuando tenemos estados de muerte, se toma el convenio de no
dibujarlos.
En este ltimo autmata,
Si w = aaab. El autmata acepta la cadena, puesto que para en 2,
que es estado de aceptacin.
Si w = bbba. El autmata rechaza la cadena, puesto que para en 3,
que no es un estado de aceptacin.
Ejemplo
Hacer el autmata que reconozca este lenguaje:
(a|b)aba*
En este diagrama de transiciones, se ve que se ha omitido
un estado de muerte, porque por ejemplo el estado 1 no
tiene transicin con el smbolo "b", y va a parar a dicho
estado de muerte. Igual pasa con el estado 2 y el smbolo
"a", y el estado 3 con el smbolo "b"
Ejemplo
Hacer el diagrama de transiciones con esta
definicin del autmata:
Q={0,1,2,3}
={a, b}
q 0 =0
F={0, 1, 2}
Como vemos, el estado 3 es un estado de muerte y poda haberse
omitido.
Este autmata, por ejemplo, acepta combinaciones de cadenas que no
tengan 3 "b seguidas.
Q={q 0 ,q 1 }
={0, 1} F={q 0 }
q 0 =q 0
Ejemplo
Suponiendo ={0, 1}, dibujar los diagramas
de transicin que reconozcan.
Cadenas terminadas en 00
Cadenas con dos "unos" consecutivos.
Cadenas que no contengan dos "unos"
consecutivos.
Cadenas con dos "ceros" consecutivos o dos "unos"
consecutivos.
Cadenas con dos "ceros" consecutivos y dos "unos"
consecutivos.
Cadenas acabadas en 00 o 11.
Cadenas con un "uno" en la antepenltima
posicin.
Cadenas de longitud 4.
Ejemplo
El estado 0, para el smbolo "a" tiene dos
transiciones, una al estado 1 y otra al estado
4, es decir, (0, a) = {1, 4}.
Q={0,1,2,3,4}
F={3,4}
={a, b}
q 0 =0
Disear un AFD para una mquina despachadora de dulces que acepta monedas de $1,
$2, y $10. El valor de los dulces es de $10. La mquina no esta diseada para dar
cambio.
10
10
10
10
q0
q1
2
q2
2
q3
2
q4
2
q5
2
10
q6
2
q7
10
q8
2
q9
2
10
10
q10
Disear un AFD que acepte el = {0,1} donde las cadenas vlidas son
donde los unos aparecen en forma par
0
q0
0
q1
1
1
0
q2
Determinar el lenguaje que aceptan los siguientes autmatas
1)
2)
q0
q0
q1
q1
q2
q2
q3
a
q1
q0
3)
b
q2
L= a*ab ( ba* ab )*
L= b|abb*
q3
q4
b
L= a(aa)*bb*a(aa*b)*
Disear un autmata finito determinstico que acepte la sucesin
5,10,20,40,80.. En binario
0
q0
q1
q2
binario
Decimal
1010
10
101
10100
101000
1010000
20
40
80
q3
Resumen
