construccion de thompson
DESCRIPTION
construccion de thompson afn Teoria computacionalTRANSCRIPT
-
Clase 09: AFN, AFD y Construccin de Thompson
Solicitado: Ejercicios 07: Construccin de AFN scon Thompson
1M. en C. Edgardo Adrin Franco Martnez http://computacion.cs.cinvestav.mx/~efranco
@efranco_escom
-
Contenido Autmata finito
Clasificacin de los autmatas finitos
Autmata finito no determinista (AFN)
Autmata finito determinista (AFD)
Teorema sobre la transformacin de AFN en AFD
Transformacin de una expresin regular en un autmata
finito
Construccin de Thompson de un AFN a partir de una
expresin regular
Nomenclatura de Thompson
Ejemplos
Ejercicios 07: Construccin de AFNs con Thompson 2
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
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.
3
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
Clasificacin de los autmatas finitos La funcin f: E*x QQ, es en general no determinista. As en
funcin de f, se hablar de autmatas finitos deterministas
AFD y autmatas finitos no deterministas AFN.
Un autmata finito no determinista AFN se caracteriza por la
posibilidad de que dada una entrada e en un estado qi, se pueda
pasar a un estado qj, qk,...,qn sin saber a ciencia cierta, a cual de esos
estados pasar. Existiendo la misma probabilidad de que pase a
cualquiera de dichos estados.
Un autmata finito determinista AFD es un caso particular de los
autmatas finitos, en el que la funcin de transicin no presenta
ninguna ambigedad en las transiciones de estados para una
entrada dada.4
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
Autmatas finitos no deterministas (AFN)
La definicin de autmata finito no determinista
AFN o AFN coincide con la de autmata finito:
AFN=(E, Q, f, q1, F)
Con la salvedad de que f: E*x QQ es no determinista,
i.e. es aquel que presenta cero, una o ms transiciones
por el mismo carcter del alfabeto.
5
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
AFN Ejemplo Resolver:
6
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
Solucin:
7
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
Autmatas finitos deterministas (AFD) Un autmata finito determinista AFD es un caso
particular de los autmatas finitos, en el que la
funcin de transicin no presenta ninguna
ambigedad en las transiciones de estados para una
entrada dada.
Un autmata finito determinista es una quntupla
AFD=(E, Q, f, q1, F) donde la funcin f: E*x QQ es
determinista.
8
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
Teorema sobre la transformacin de AFN en AFD
"Para todo autmata finito no determinista AFN=(E,
Q, f, q1,F) se puede construir un autmata finito
determinista AFD=(E, Q, f, q1, F) tal que el
lenguaje reconocido por el autmata finito
determinista AFD coincida con el lenguaje
reconocido por el autmata finito no determinista
AFN, es decir L(AFD) = L(AFN)".
9
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
Transformacin de AFN en AFD
Expresin: ab|ac*
AFN
ab
a
2
1
c
3
4
INICIO
10
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
AFD
Expresin: ab|ac*
ba
1
c
3
4
2,4
c
INICIO
11
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
Transformacin de una expresin regular en un autmata
finito
Dada una expresin regular existe un autmata
finito capaz de reconocer el lenguaje que sta define.
Recprocamente, dado un autmata finito, se puede
expresar mediante una expresin regular del
lenguaje que reconoce.
12
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
((a+b)(a(bba* + aa) + ba))(b*)
-
Transformacin de una expresin regular en un autmata
finito
13
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
14
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
15
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
Construccin de Thompson de un AFN a partir de
una expresin regular
La construccin de Thompson construye un AFN a
partir de cualquier expresin regular.
La construccin de Thompson construye a partir de
una expresin regular r un AFN que reconoce el
lenguaje definido por r, esto se realiza con el
objetivo de que en un algoritmo siguiente se pueda
generar un AFD mnimo equivalente.
Utiliza una notacin estndar para generar el AFN16
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
Para la representacin de una cadena vaca se utiliza
el smbolo o
Nomenclatura de Thompson
Cadena Vaca
17
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
Para representar un smbolo, se utilizan dos
estados y una transicin para el movimiento con el
smbolo.
r
18
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
Para la concatenacin de dos smbolos nicamente
se unen
rs
Concatenacin de smbolo
19
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
Para la eleccin de alternativas, crear transiciones
para la unin de las transiciones.
r | s
Eleccin de alternativas
20
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
Para la cerradura positiva, se agregan transiciones
para retornar al estado previo, permitiendo agregar
1 o mas veces el smbolo
r +
Cerradura positiva
21
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
Para la cerradura de Kleene, se agregan
transiciones para retornar a estado previo. Y otra
transicin para saltar la transicin con r.
r *
Cerradura de Kleene
22
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
Diagrama del AFN que representa la ER a*b.
1. Parte de la cerradura de Kleene.
Ejemplo 01 Mtodo de Thompson
a*b
23
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
2. Para continuar se generan la concatenacin del
smbolo b
a*b
24
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
3. Para finalizar se numeran los estados y se indica el
estado inicial y final
a*b
q0
q1 q2
q3
25
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
q4
-
4. Formalizando
AFN=(E,Q,f,q0,F)
E={a,b}
Q={q0,q1,q2,q3,q4}
F={q4}
f: E*x QQ
L(a*b)=L(AFN)
26
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
f a b
q0 - - {q1, q3}
q1 q2 - -
q2 - - {q1, q3}
q3 - q4 -
q4 - - -
-
A partir de la ER (b|(b*a)*)a
1. Parte de la cerradura de Kleene que se encuentra
dentro de parntesis.
Ejemplo 02 Mtodo de Thompson
(b|(b*a)*)a
27
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
A partir de la ER (b|(b*a)*)a
2. Completamos dicho parntesis concatenando el
smbolo a
(b|(b*a)*)a
28
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
A partir de la ER (b|(b*a)*)a
3. Aplicar la Cerradura de Kleene al parntesis
(b|(b*a)*)a
29
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
A partir de la ER (b|(b*a)*)a
4. La eleccin de alternativas del b y el diagrama
anterior.
(b|(b*a)*)a
30
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
5. Concatenamos el ltimo smbolo, enumerando e
indicando el estado inicial y el final
(b|(b*a)*)a
31
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
-
6. FormalizandoAFN=(E,Q,f,q0,F)
E={a,b}
Q={q0,q1,q2,q3,q4, q5,q6,q7,q8,q9,q10,q11}
F={q11}
f: E*x QQ
L((b|(b*a)*)a)=L(AFN)
32
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z
f A b
q0 - - {q1, q8}
q1 - - {q2, q7}
q2 - - {q3, q5}
q3 - q4 -
q4 - - q5
q5 q6 - -
q6 - - {q7, q2}
q7 - - q10
q8 - q9 -
q9 - - q10
q10 q11 - -
Q11 - - -
-
Ejercicios 07: Construccin de AFNs con Thompson
Construir grafica y formalmente los autmatas para las siguientesexpresiones regulares a travs de la nomenclatura de Thompson.
1. (abc)*
2. (b|bc)+
3. letra_(letra_|digito)*
4. (a|b)*abb
5. [(b|b*a)*]a
6. (a*|b+) +
*Se entregarn antes del da Lunes 30 de Septiembre de 2013(23:59:59 hora limite).
*Sugerencia utilizar Jflap para el dibujo y simulacin de los autmatas
*Incluir la redaccin de cada ejercicio
*Portada y encabezados de pagina33
T
e
o
r
a
c
o
m
p
u
t
a
c
i
o
n
a
l
C
l
a
s
e
0
8
:
A
F
N
,
A
F
D
y
C
o
n
s
t
r
u
c
c
i
n
d
e
T
h
o
m
p
s
o
n
P
r
o
f
.
E
d
g
a
r
d
o
A
d
r
i
n
F
r
a
n
c
o
M
a
r
t
n
e
z