Autômatos Finitos com Transições Vazias

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

AUTÔMATOS FINITOS COM
TRANSIÇÕES VAZIAS
Marcelo Guerra
INTRODUÇÃO
 Um AFN tem permissão para fazer mudanças de
estado espontâneas, sem influência da entrada.
 Permite-se transições sobre ε (epsílon).
 É permitido que ε seja o segundo argumento da
função δ.
 ε-transição
 Ex: AFN para cadeias do tipo 0n1m2p com n,m,p ≥ 0.
q1q0 q2
Início ε ε
0 1 2
E-TRANSIÇÕES
 Considere o diagrama abaixo, onde cada ε
encontrado em um rótulo entre o estado inicial e
um estado final não influi na cadeia reconhecida.
q1q0 q5
início
.
0,1,…,9
q4
q2 q3
0,1,…,9
ε,+,- . ε
0,1,…,9
0,1,…,9
NOTAÇÃO
 A representação de um ε-AFN é a mesma usada
para AFN’s, exceto para a função de transição
que deve incluir transições vazias.
 Seja A = (Q,Σ,δ,q0,F), então δ é a função que
recebe como argumentos:
 Um estado em Q
 Um elemento de Σ ∪ {ε}
NOTAÇÃO
 A = ({q0, q1, ..., q5}, {., +, -, 0, 1, ..., 9}, , q0, {q5}),
onde é definido pela tabela abaixo:
+, - . 0, 1, ..., 9
q0 {q1} {q1}
q1 {q2} {q1, q4}
q2 {q3}
q3 {q5} {q3}
q4 {q3}
q5
q1q0 q5
início
.
0,1,…,9
q4
q2 q3
0,1,…,9
ε,+,- . ε
0,1,…,9
0,1,…,9
Ε-FECHAMENTOS
 A definição de função estendida para ε-AFN’s
permite explicar por que esses autômatos são
equivalentes aos AFD’s.
 Para isso, é necessário entender a noção de
ε-fechamento para estados.
 A seqüência de todos os estados alcançáveis saindo
de um estado através de transições vazias
DEFINIÇÃO
 Base: o estado q está em -FECHO(q)
 Indução: se o estado p está em -FECHO(q), e
existe uma transição de p para o estado r
rotulada ε, então r está em -FECHO(q).
EXEMPLO
 -FECHO(q0) = {q0, q1}
 -FECHO(q3) = {q3, q5}
q1q0 q5
início
.
0,1,…,9
q4
q2 q3
0,1,…,9
ε,+,- . ε
0,1,…,9
0,1,…,9
EXEMPLO
 -FECHO(1) = {1, 2, 3, 4, 6}
1
54
2 3
ε
ε
7
6
ε
a
b
ε
ε
DEFINIÇÃO DE δ*
 Seja A = (Q, Σ, δ, q0, F) um ε-AFN. A função de transição
estendida - δ*(q,w) - será o conjunto de estados cujos
rótulos, quando concatenados, formam a string w.
 Base: δ*(q,ε) = -FECHO(q)
 Indução: suponha que w seja da forma xa. Então δ* é
definido por:
 Seja {p1, ..., pk} o valor de δ*(q,x).
 Seja = {r1, ..., rm}
 Então δ*(q,w) =

m
j
jrFECHO
1
)(
EXERCÍCIO
 Encontre:
 δ*(q0,aa)
 δ*(q0,aaa)
q1q0 q2
Início a a
ε
EXERCÍCIO
 Encontre:
 δ*(q0,aa)=δ (q0,a) → δ (qn,aa)...
 δ (q0,a)
 δ (q0,a) ={q1}
 -FECHO(q1) ={q1}
 δ (q0,aa)
 δ (q1,a)={q2}
 -FECHO(q2) ={q0, q2}
 δ*(q0,aaa)= δ (q0,a) → δ (qn,aa)...
 δ (q0,aaa)= δ(q0,a) U δ(q2,a)= {q1}
 -FECHO(q1) ={q1}
q1q0 q2
Início a a
ε
A LINGUAGEM DE UM ε-AFN
 Seja E = (Q, Σ, δ, q0, F), então
 L(E) = {w | δ*(q0, w) ∩ F ≠ }
 Em palavras, a linguagem contém todas as cadeias
w, para as quais existe um caminho, rotulado w, do
vértice inicial do grafo de transição a algum vértice
final.
ELIMINAÇÃO DE ε-TRANSIÇÕES
 Dado qualquer ε-AFN podemos encontrar um AFD
que reconhece a mesma linguagem.
 O processo é similar à construção de subconjuntos.
 Porém devemos incorporar as ε-transições, o que é
feito através do ε-fechamento.
ALGORITMO
 Sejam E = (QE, Σ, δE, q0, FE) e D = (QD, Σ, δD, qD,
FD) definido como a seguir:
1. QD é o conjunto de subconjuntos de QE , isto é S’ ⊆
QE tais que S’ = -FECHO(S).
2. qD = -FECHO(q0)
3. FD representa os conjuntos de estados que contêm
pelo menos um estado de aceitação de E.
ALGORITMO (CONT.)
4. δD(S, a) é calculado para todo a ∈ Σ e todo S em QD
por:
 Seja S = {p1, …, pk}
 Calcule . Seja esse conjunto {r1,…, rm}
 Então δD(S, a) = 

m
j
jrFECHO
1
)(
ELIMINAÇÃO DE ε-TRANSIÇÕES
 Converter o AFN num AFD equivalente.
 ε-fecho (q0) = {q0,q1,q2}
 δD({q0, q1 ,q2},0) = ε-fecho(δN(q0,0)) U ε-fecho(δN(q1,0)) U ε-fecho(δN(q2,0))
= ε-fecho ({q0}) U ε-fecho ({ }) U ε-fecho (q2)
= {q0, q1 ,q2} U { } U {q2} = {q0, q1 ,q2}
 δD({q0, q1 ,q2},1) = ε-fecho(δN(q0,1)) U ε-fecho(δN(q1,1)) U ε-fecho(δN(q2,1))
= ε-fecho ({ }) U ε-fecho ({q1}) U ε-fecho ({ })
= {} U {q1 ,q2} U {} = {q1 ,q2}
 ...
q1q0 q2
Início ε ε
0 1 0
ELIMINAÇÃO DE ε-TRANSIÇÕES
 Converter o AFN num AFD equivalente.
 ε-fecho (q0) = {q0,q1,q2}
 δD({q0, q1 ,q2},0) = ε-fecho(δN(q0,0)) U ε-fecho(δN(q1,0)) U ε-fecho(δN(q2,0))
= ε-fecho ({q0}) U ε-fecho ({ }) U ε-fecho (q2)
= {q0, q1 ,q2} U { } U {q2} = {q0, q1 ,q2}
 δD({q0, q1 ,q2},1) = ε-fecho(δN(q0,1)) U ε-fecho(δN(q1,1)) U ε-fecho(δN(q2,1))
= ε-fecho ({ }) U ε-fecho ({q1}) U ε-fecho ({ })
= {} U {q1 ,q2} U {} = {q1 ,q2}
 δD({q1 ,q2},0)= ε-fecho(δN(q1,0)) U ε-fecho(δN(q2,0)) ={} U {q2}
 δD({q1 ,q2},1)= ε-fecho(δN(q1,1)) U ε-fecho(δN(q2,1)) = {q1,q2} U {}
q1q0 q2
Início ε ε
0 1 0
ELIMINAÇÃO DE ε-TRANSIÇÕES
 Converter o AFN num AFD equivalente.
 ε-fecho (q0) = {q0,q1,q2}
 δD({q0, q1 ,q2},0) = ε-fecho(δN(q0,0)) U ε-fecho(δN(q1,0)) U ε-fecho(δN(q2,0))
= ε-fecho ({q0}) U ε-fecho ({ }) U ε-fecho (q2)
= {q0, q1 ,q2} U { } U {q2} = {q0, q1 ,q2}
 δD({q0, q1 ,q2},1) = ε-fecho(δN(q0,1)) U ε-fecho(δN(q1,1)) U ε-fecho(δN(q2,1))
= ε-fecho ({ }) U ε-fecho ({q1}) U ε-fecho ({ })
= {} U {q1 ,q2} U {} = {q1 ,q2}
 δD({q1 ,q2},0)= ε-fecho(δN(q1,0)) U ε-fecho(δN(q2,0)) ={q2}
 δD({q1 ,q2},1)= ε-fecho(δN(q1,1)) U ε-fecho(δN(q2,1)) = {q1,q2}
q1, q2q0,q1,q2 q2
Início 1 0
0 1 0
ELIMINAÇÃO DE ε-TRANSIÇÕES
 Converter o AFN num AFD equivalente.
q1, q2q0,q1,q2 q2
Início 1 0
0 1 0
q1q0 q2
Início ε ε
0 1 0
EXEMPLO
 Converta o seguinte autômato em um AFD
q1q0 q5
início
.
0,1,…,9
q4
q2 q3
0,1,…,9
ε,+,- . ε
0,1,…,9
0,1,…,9
EXEMPLO
TEOREMA
 Uma linguagem L é aceita por algum ε-AFN sse
ela é aceita por algum AFD.