Clase_08

Vista previa del material en texto

Clase 08: Autómatas finitos
Solicitado: Ejercicios 06: Autómatas finitos
1M. en C. Edgardo Adrián Franco Martínez 
http://computacion.cs.cinvestav.mx/~efranco
@efranco_escom
edfrancom@ipn.mx
Contenido
• Autómata finito 
• Definición formal de autómata finito
• Configuración de un autómata finito
• Lenguaje reconocido por un autómata finito
• Ejemplos
• Ejemplo 1
• Ejemplo 2
• Ejemplo de programación en C
• Ejercicios 06: Autómatas finitos
2
Te
o
rí
a
 c
o
m
p
u
ta
ci
o
n
a
l
C
la
se
 0
8
: 
A
u
tó
m
a
ta
s 
fi
n
it
o
s
P
ro
f.
 E
d
ga
rd
o
 A
d
ri
á
n
 F
ra
n
co
 M
a
rt
ín
e
z
Autómata finito
• Un autómata finito es un modelo matemático de
una máquina que acepta cadenas de un lenguaje
definido sobre un alfabeto A.
• Consiste en un conjunto finito de estados y un
conjunto 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. 3
Te
o
rí
a
 c
o
m
p
u
ta
ci
o
n
a
l
C
la
se
 0
8
: 
A
u
tó
m
a
ta
s 
fi
n
it
o
s
P
ro
f.
 E
d
ga
rd
o
 A
d
ri
á
n
 F
ra
n
co
 M
a
rt
ín
e
z
• Los autómatas finitos reconocen los lenguajes
regulares, o de tipo 3 y se pueden representar
intuitivamente por una cinta y una cabeza de lectura.
•La cinta de entrada, sólo contiene
símbolos de un determinado
alfabeto, y se mueve en una sólo
dirección.
•El control de estados, determina el
funcionamiento del autómata.
•Una sentencia de un lenguaje
determinado, colocada en la cinta, y
leída por el autómata finito, es
reconocida por éste, si el control de
estados llega a un estado final.
4
Te
o
rí
a
 c
o
m
p
u
ta
ci
o
n
a
l
C
la
se
 0
8
: 
A
u
tó
m
a
ta
s 
fi
n
it
o
s
P
ro
f.
 E
d
ga
rd
o
 A
d
ri
á
n
 F
ra
n
co
 M
a
rt
ín
e
z
Definición formal de autómata finito
• Un autómata finito es una quíntupla A = ( E, Q, f, q0, F ) 
donde:
• E = {conjunto de entradas o vocabulario de entrada} 
• E es un conjunto finito, y sus elementos se llaman entradas o símbolos 
de entrada.
• Q = {conjunto de estados} 
• Q es el conjunto finito de estados
• f: E*x Q→Q es la función de transición o función del estado siguiente
• Para un par del conjunto E × Q devuelve un estado perteneciente al conjunto Q, 
y es el producto cartesiano de E por Q.
• q0 Є Q, es el estado inicial
• F ⊂ Q, es el conjunto de estados finales
5
Te
o
rí
a
 c
o
m
p
u
ta
ci
o
n
a
l
C
la
se
 0
8
: 
A
u
tó
m
a
ta
s 
fi
n
it
o
s
P
ro
f.
 E
d
ga
rd
o
 A
d
ri
á
n
 F
ra
n
co
 M
a
rt
ín
e
z
Configuración de un autómata finito
• Se entiende por configuración de un autómata
finito, a un par de la forma (q, W) donde q, es el
estado actual, y W la cadena que queda por leer en
ese instante.
• La configuración inicial de un autómata finito es el
par (q0 , t) siendo t la sentencia o cadena de entrada
a reconocer.
• La configuración final se representa por el par (qi , λ)
donde qi Є F, y λ indica que no queda nada por entrar de la
cinta.
6
Te
o
rí
a
 c
o
m
p
u
ta
ci
o
n
a
l
C
la
se
 0
8
: 
A
u
tó
m
a
ta
s 
fi
n
it
o
s
P
ro
f.
 E
d
ga
rd
o
 A
d
ri
á
n
 F
ra
n
co
 M
a
rt
ín
e
z
• Un movimiento de un autómata finito, puede
definirse como el transito entre dos configuraciones,
y se representa por (q , aW) → (q', W) y se debe de
cumplir que f(q , a)=q'.
• Un autómata finito es una maquina de estados
capaz de reconocer un lenguaje regular. Si el
autómata es capaz de alcanzar en su configuración
final.
7
Te
o
rí
a
 c
o
m
p
u
ta
ci
o
n
a
l
C
la
se
 0
8
: 
A
u
tó
m
a
ta
s 
fi
n
it
o
s
P
ro
f.
 E
d
ga
rd
o
 A
d
ri
á
n
 F
ra
n
co
 M
a
rt
ín
e
z
Lenguaje reconocido por un autómata finito
• Cuando un autómata transita a una configuración final
partiendo de la configuración inicial, en varios movimientos,
se dice que se ha producido aceptación o reconocimiento de
la cadena de entrada. Es decir que dicha cadena, pertenece al
lenguaje reconocido por el autómata.
• Por el contrario, cuando el autómata finito no es capaz de
llegar a un estado final, se dice que el autómata no reconoce
dicha cadena y que por tanto no pertenece al lenguaje.
8
Te
o
rí
a
 c
o
m
p
u
ta
ci
o
n
a
l
C
la
se
 0
8
: 
A
u
tó
m
a
ta
s 
fi
n
it
o
s
P
ro
f.
 E
d
ga
rd
o
 A
d
ri
á
n
 F
ra
n
co
 M
a
rt
ín
e
z
• Para toda gramática regular "tipo 3", existe un autómata
finito "AF", tal que el lenguaje reconocido por el autómata
finito es igual al lenguaje generado por la gramática.
• La forma habitual de representar los autómatas finitos es
mediante un grafo o diagrama de estados, donde los nodos
son los estados y las ramas están marcadas con los símbolos
del alfabeto de entrada. Las ramas se construyen según la
función de transición, así debe de cumplir .
9
Te
o
rí
a
 c
o
m
p
u
ta
ci
o
n
a
l
C
la
se
 0
8
: 
A
u
tó
m
a
ta
s 
fi
n
it
o
s
P
ro
f.
 E
d
ga
rd
o
 A
d
ri
á
n
 F
ra
n
co
 M
a
rt
ín
e
z
• Los nodos que representan los estados finales, suelen marcarse con 
un doble círculo, y el estado inicial también se marca con una 
flecha, encima de la cual se coloca la palabra INICIO.
10
Te
o
rí
a
 c
o
m
p
u
ta
ci
o
n
a
l
C
la
se
 0
8
: 
A
u
tó
m
a
ta
s 
fi
n
it
o
s
P
ro
f.
 E
d
ga
rd
o
 A
d
ri
á
n
 F
ra
n
co
 M
a
rt
ín
e
z
abc*
Ejemplo 01
11
Te
o
rí
a
 c
o
m
p
u
ta
ci
o
n
a
l
C
la
se
 0
8
: 
A
u
tó
m
a
ta
s 
fi
n
it
o
s
P
ro
f.
 E
d
ga
rd
o
 A
d
ri
á
n
 F
ra
n
co
 M
a
rt
ín
e
z
Ejemplo 01: Solución
• Solución: Se construye el diagrama de estados, colocando en
primer lugar todos los estados dentro de círculos, marcando
con doble círculo el estado final. El estado inicial se indica con
una flecha que lo señala 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 símbolo del vocabulario de entrada a.
De igual forma se recorre la tabla de transiciones para cada
estado y entrada completándose el diagrama de Moore.
12
Te
o
rí
a
 c
o
m
p
u
ta
ci
o
n
a
l
C
la
se
 0
8
: 
A
u
tó
m
a
ta
s 
fi
n
it
o
s
P
ro
f.
 E
d
ga
rd
o
 A
d
ri
á
n
 F
ra
n
co
 M
a
rt
ín
e
z
Ejemplo 01: Lenguaje reconocido por un autómata finito
1313
Te
o
rí
a
 c
o
m
p
u
ta
ci
o
n
a
l
C
la
se
 0
8
: 
A
u
tó
m
a
ta
s 
fi
n
it
o
s
P
ro
f.
 E
d
ga
rd
o
 A
d
ri
á
n
 F
ra
n
co
 M
a
rt
ín
e
z
Ejemplo 02
14
• Los identificadores de C son cadenas de letras, dígitos y guiones 
bajos. 
letra_ → [A-Za- z_] 
dígito → [0-9]
id → letra_ ( letra_ | dígito)* 
14
Te
o
rí
a
 c
o
m
p
u
ta
ci
o
n
a
l
C
la
se
 0
8
: 
A
u
tó
m
a
ta
s 
fi
n
it
o
s
P
ro
f.
 E
d
ga
rd
o
 A
d
ri
á
n
 F
ra
n
co
 M
a
rt
ín
e
z
Ejemplo 02: Solución
• Solución : Este ejemplo es inverso al anterior, pues se da un
lenguaje y se pide el autómata que lo reconoce. En primer
lugar se construye un diagrama de Moore, de tal forma que a
partir del estado inicial, después de leer una letra, acepte
letras o dígitos de forma variable, y cuando encuentre un
carácter diferente de letra o dígito alcance el estado final. El
diagrama de Moore es el que se muestra en la figura.
15
Te
o
rí
a
 c
o
m
p
u
ta
ci
o
n
a
l
C
la
se
 0
8
: 
A
u
tó
m
a
ta
s 
fi
n
it
o
s
P
ro
f.
 E
d
ga
rd
o
 A
d
ri
á
n
 F
ra
n
co
 M
a
rt
ín
e
z
Ejemplo 02: Solución
• $ representa a el fin de la cadena
• El autómata finito se deduce del diagrama de estaos y es el 
siguiente:
• donde f se define por :
16
Te
o
rí
a
 c
o
m
p
u
ta
ci
o
n
a
l
C
la
se
 0
8
: 
A
u
tó
m
a
ta
s 
fi
n
it
o
s
P
ro
f.
 E
d
ga
rd
o
 A
d
ri
á
n
 F
ra
n
co
 M
a
rt
ín
e
z
Ejemplo de programaciónen C
Programa que modela el AF=(E,Q,f,q0,F) donde:
E={a,b}, Q={q0, q1, q2, q3}, F={q1, q2}
f:ExQ->Q
f(q0,a)=q1
f(q0,b)=q3
f(q1,a)=q1
f(q1,b)=q2
f(q2,a)=q3
f(q2,b)=q2
f(q3,a)=q3
f(q3,b)=q3
17
Te
o
rí
a
 c
o
m
p
u
ta
ci
o
n
a
l
C
la
se
 0
8
: 
A
u
tó
m
a
ta
s 
fi
n
it
o
s
P
ro
f.
 E
d
ga
rd
o
 A
d
ri
á
n
 F
ra
n
co
 M
a
rt
ín
e
z
AF que describe el lenguaje dado por la
expresión regular a+b*. "L(AF)=L(a+b*)"
//LIBRERIAS Y DEFINICIONES DE CONSTANTES
#include <stdio.h >
#define FIN_CADENA ' \ n'
//Modelado de los estados
enum{q0,q1,q2,q3};
//PROGRAMA PRINCIPAL
int main (void )
{
int estado =q0; //Estado = Estado inicial q0
char entrada ; // Caracter de entrada
entrada =getchar (); //Leer la primer entrada
//Ciclo que modela transicin del automata conforme avanza el cabezal de lectura
while(entrada !=FIN_CADENA) //Mientras la entrada no sea el final de la cadena
{
switch(estado )
{
case q0: //Modelado de las transiciones del estado q0
if(entrada =='a' ) estado =q1;
else if(entrada =='b' )estado =q3;
break;
case q1: //Modelado de las transiciones del estado q1
if(entrada =='a' ) estado =q1;
else if(entrada =='b' )estado =q2;
break;
case q2: //Modelado de las transiciones del estado q2
if(entrada =='a' ) estado =q3;
else if(entrada =='b' )estado =q2;
break;
case q3: //Modelado de las transiciones del estado q3
if(entrada =='a' ) estado =q3;
else if(entrada =='b' )estado =q3;
break;
default:
break;
}
entrada =getchar (); //Leer de la segunda a más entradas
}
//Comprobar si al alcanzar la configuración final e l automata alcanzo un estado final
if(estado ==q1||estado ==q2) printf (" \ nCadena VALIDA en el lenguaje L( a+b*)" );
else printf (" \ nCadena NO VALIDA en el lenguaje L( a+b*)" );
return 0; //Fin de programa
}
18
Te
o
rí
a
 c
o
m
p
u
ta
ci
o
n
a
l
C
la
se
 0
8
: 
A
u
tó
m
a
ta
s 
fi
n
it
o
s
P
ro
f.
 E
d
ga
rd
o
 A
d
ri
á
n
 F
ra
n
co
 M
a
rt
ín
e
z
Ejercicios 06: Autómatas finitos
1. Diseñe autómatas finitos capaces de reconocer los siguientes
lenguajes definidos por la expresiones regulares:
i. a+b*
ii. ab(cd)+e
iii. (a+b+)cd
iv. abz?b+
v. (cg)*gato+ |cd
2. Programe los autómatas finitos diseñados anteriormente y
verifique su funcionamiento.
*Se entregarán antes del día Viernes 27 de Septiembre de 2013
(23:59:59 hora limite)
*Sugerencia utilizar Jflap para el dibujo y simulación de los autómatas 
*Incluir la redacción de cada ejercicio
*Portada y encabezados de pagina
*Incluir pantallazos del funcionamiento y pruebas
19
Te
o
rí
a
 c
o
m
p
u
ta
ci
o
n
a
l
C
la
se
 0
8
: 
A
u
tó
m
a
ta
s 
fi
n
it
o
s
P
ro
f.
 E
d
ga
rd
o
 A
d
ri
á
n
 F
ra
n
co
 M
a
rt
ín
e
z