Autómatas finitos
Tomado de Sudkamp:
Languages and Machines
Cap. 6.
Autómatas Finitos
(determinísticos)
M=(,Q,,q0,F)
Alfabeto
Estado
inicial
Función de
transición
Conjunto
de
estados

Q
a
b
q0
q1
q0
q1
q1
q2
q2
q2
q2
Estados
finales
 :Q   Q
b a
q0
a
q1
a
b
b
q2
Funcionamiento del
M=(,Q,,q0,F)
autómata
 :Q   Q
*
 *  qi ,    qi
Palabras que
contienen a ab
b
a
q0
q1
a
b
b
*
a
 *  qi ,  u     *  qi ,   , u 
q2
L ( M )   :  *  q 0 ,    F 
*(aab,q1)=  (*(aa,q1),b)= (  (*(a,q1),a),b)=  ((  (*(,q1),a),a),b)=
 ((  (q1,a),a),b)=  (( q1,a),b)=  ( q1,b)= q2
[q1,aab][q1,ab][q1,b][q2,]
Ejemplos
q2
q1
Palabras que contienen
exactamente 2 a’s
Palabras que contienen
exactamente 3k b’s
q0
q3
q2
b
b a
Lenguaje representado por la
expresión aa*b
q1
q0
q0
q1
b
b aa
q2
q3
a
Autómatas finitos no
determinísticos
q1
q0
q2
q1
q0
q1
q0
q2
q2
q0
q1
q2
q3
Autómatas finitos no
determinísticos
Palabras que empiezan por ab y
terminan con ba
q0
q1
q2
q3
q4
q5
q6
a(ba wb(awb)*ba)
Autómatas finitos no
determinísticos
M=(,Q,,q0,F)
 : Q    ( Q )
q1
q0
q2
q0
q4
q3
q1
q2
q3
q4

a
q1

q2
q4
b

q2
q2,q3


Autómatas finitos no
determinísticos
 : Q    ( Q )
M=(,Q,,q0,F)
 : Q    ( Q )
*
*
q j   ( q i , wu )   q k ( q k   ( q i , w )  q j   ( q k , u ))
*
qi
*
w
qk
u
qj
Autómatas FND
 : Q    ( Q )
M=(,Q,,q0,F)
 : Q    ( Q )
*
*
L ( M )  { w   |  q  F ( q   ( q o , w ))}
*
*
Ejemplos AFND
Ejemplos AFND (6.4.6)
{, ab, aabb, aaabbb} { a i b i | 0  i  n}
¿ { a b | i  0} ?
i
i
Autómatas con transiciones 
-AFN
 : Q  (   { })   ( Q )
M=(,Q,,q0,F)
q10
b
q11
b
a,b

q12
q20
a,b
b
q10
b
q11
a
b
b
q0

L(M )  L(M 1)  L(M 2 )
q12
a,b
a,b
q20
q21
a
b
q21
a,b
Clausura con -AFN
L(M )  L(M 1)  L(M 2 )
M1
L(M )  L(M 1)L(M 2 )
M2
M1

Si M1 y M2 son -AFN
existen -AFN tales
que:



M2
L(M )  L(M 1)
*
Clausura con -AFN
L(M )  L(M 1)  L(M 2 )
M1
L(M )  L(M 1)L(M 2 )
M2
q11

Si M1 y M2 son -AFN
existen -AFN tales
que:
L(M )  L(M 1)

M1

M2


M1

*
Concluimos….
• Toda expresión regular tiene al menos un
correspondiente -AFND que acepta
exactamente las palabras
correspondientes a la expresión.
Eliminando el indeterminismo
La clausura Lambda, para cada estado qi, se
construye recursivamente así:
BASE:
q i    Cl ( q i )
( q j    Cl ( q i )  q k   ( q j ,  )) 
Paso
recursivo q    Cl ( q )
k
i
La función de transición de entradas t para un
-AFND se define así:
t : Q    ( Q )
t (qi , a ) 
   Cl ( ( q
q j    Cl ( q i )
j
, a ))
Ejemplo 6.6.1
a
q0
a
a
q2

q1
c
b

q0
q1
a
q0,q1,q2


b


q2
c



q1
q2


q2
t
q0
q1
q2
a
q0,q1,q2


b

q2
q2
c

q1,q2

Algoritmo 6.6.3
Construction of DM, a DFA Equivalent to NFA- M
Input: an NFA- M=(Q,,,q0,F).
input transition fuction t of M
1. initialize Q’ to -Cl(q0)
2. repeat
2.1 if there is a node XQ’ and a symbol a with no arc leaving X labeled a then
2.1.1 let Y   t ( q i , a )
qi  X
2.1.2 if Y  Q ' then set
Q ' : Q ' {Y }
2.1.3 add an arc from X to Y labeled a
else done:=true
until done
3. The set of accepting states of DM is F’={XQ’| X contiene algún elemento de F}
Ejemplo
a
a
q0
a
q0,q1,q2
b

q1
q2


q2

c
a
q0
t
q2

q1,q2
q2

q1
b
b,c
q0

a,c
a
c
a
q0,q1,q2
a
q2
b
c
b
q1,q2
c
a,b,c
b
Grafos de expresiones
a*ba*ba*ba*
a*ba*b
q1
q0
q2
q0
q2
(a*ba*ba*ba*)*
q0
Eliminar el estado intermedio i
j
wji
wik
i
k
wji wik
j
k
wii
j
wji
i
wik
k
j
wji (wii)*wik
i debe ser diferente de j y de k pero puede ser j=k
k
Situaciones finales
w
W*
w1
w2
w4
w3
w1* w2(w3 w w4w1*w2)*
Grafos de expresiones
q1
q0
ba*b
q2
q0
q2
(a*ba*b)(a* w ba*ba*b)*
Expresión de un AFND
(awb)*bb (awb)*w (awb)*aa (awb)*
Gramática regular para un AFND
S → aS| bB| 
B → aB| bC
C → aC| bS
q1
q0
q2
Gramática para un AFND (cont)
q0
q1
q2
q3
q4
q5
q6
S → aB
B → bC| ba
C → aC| bC | ba
S → aB
B → bC| bD
C → aC| bC | bE
D→a
E→a
S → aB
B → bC| bD
C → aC| bC | bE
D → aF
E → aG
F→
G→
AFND para un gramática regular
• Palabras sobre {a,b,c} que contiene al
menos una c pero no contienen cc.
S → aS| bS |cA
A → aS| bS| 
a,b
a,b
q0
c
q1
Lenguajes regulares
Expresiones
Regulares
AFD
No son LR:
 a b : i  0
 a b a : i , j  0
i
AFND
Gramáticas Regulares
i
 
i
j
i
R
:    *

:



*






:



*


prim
o


R

Pre-Lema de bombeo
• Sea w1,w2,w3,w4,…. y v1,v2,v3,v4,…
sucesiones infinitas de palabras.
• Si L es un lenguajes tal que wivj pertenece
a L si y sólo sí i=j.
• Entonces L no es regular.
Si existiera un autómata finito de k estados existen i<j tal
que *(q0,wi)=*(q0,wj) y por tanto wivi y wjvj son acptadas,
contradicientdo las hipótesis.
Aplicación
• No son regulares:
a b
i
i
|i  0

a b
i
j
c | i , j  0
i
a b
i
2i
|i  0

Lema de Bombeo
q0
q1
qi
qk
Un autómata de k estados si acepta una
palabra de longitud mayor que k acepta
infinitas palabras
Si |z|>k existen u,v
y w tales que
Un autómata de k estados acepta infinitas
palabras si y solo si acepta alguna  tal
que k< || < 2k
uvnw para todo n
está en L
|uv|<k+1
|v|>0 y
Aplicación
• Las palabras cuya longitud es un
cuadrado perfecto no forman un lenguaje
regular.
Supóngase que un autómata de k estados acepta tal lenguaje,
tómese entonces una palabra z con longitud k2 , entonces
z=uvw
con |uv|k o sea |v|k y además uv2w es aceptada por el
autómata,
Pero |uv2w| no puede ser cuadrado perfecto pues:
|uv2w|= |uvw|+|v|=k2+|v| k2+k<(k+1
)2
2
2
Entre k y (k+1) no hay ningún cuadrado
perfecto !
Propiedades de
clausura
Conjuntos finitos de
palabras forman lenguajes
regulares
Unión de dos
Concatenación de dos
Intersección de dos
Complemento de
* de
...lenguajes regulares, es
un lenguaje regular
Descargar

FORMAS NORMALES - Noticias | Facultad de Ciencias de la