Autômatos e Computabilidade - Autômatos Finitos 2

Prévia do material em texto

Autômatos e computabilidade
Autômatos finitos 2
Pedro A D Rezende
UnB – IE – CIC
Cadeia vazia: l (ou e) é a cadeia tal que |l| = 0
 
A & C: Autômatos finitos 2
Trasições “espontâneas” 
Um lFA é um FA com transições por l, isto é,
 M = (Q, , q
0
, d, F) onde d  (Q(S{l}))Q. 
((q,l),q')  d seria transição de q por l para q'
omo vértices, d como arestas rotuladas
 qq' 
transição de q para q' por a
 
A & C: Autômatos finitos 2
Trasições “espontâneas” 
Um lFA é um FA com transições por l, isto é,
 M = (Q, , q
0
, d, F) onde d  (Q(S{l}))Q. 
((q,l),q')  d seria transição de q por l para q'.
omo vértices, d como arestas rotuladas
 qq' 
transição de q para q' por a
Q \ {l}
q
0
q
 ... a ... | l
{q'...}
 
A & C: Autômatos finitos 2
Comportamento de lFAs 
O comportamento de um lFA perante cadeias
de S inclui transições espontâneas (por l).
d*  (QS*)Q 
é definida indutivamente por:
 d*(q,l) = {q}l ; d*(q,a) = d(q,a)l
d*(q,aa) = d(d*(q,a),a)l 
onde Pl é o l-fecho de PQ definido por
Pl = {qQ |  caminho de rQ a q rotulado por l}
 
A & C: Autômatos finitos 2
Comportamento de lFAs 
O comportamento de um lFA perante cadeias
de S inclui transições espontâneas (por l).
d*  (QS*)Q é definida indutivamente por:
 d*(q,l) = {q}l ;
d*(q,a) = d(q,a)l ;
d*(q,aa) = d(d*(q,a),a)l .
onde Pl é o l-fecho de PQ definido por
Pl = {qQ |  caminho de rQ a q rotulado por l}
 
A & C: Autômatos finitos 2
Comportamento de lFAs 
O comportamento de um lFA perante cadeias
de S inclui transições espontâneas (por l).
d*  (QS*)Q é definida indutivamente por:
 d*(q,l) = {q}l ;
d*(q,a) = d(q,a)l ;
d*(q,aa) = d(d*(q,a),a)l 
onde, dado VQ, Vl é o fecho l de V:
Vl = {qQ |  caminho de vV a q rotulado por l}
 
A & C: Autômatos finitos 2
Modelos computacionais para LFs 
FA é um modelo para reconhecedores 
de linguagens regulares 
 aS* (string)  |d*(q
0
,a) F| (booleano de aL(M)?)
Como encontrar modelo computacional inverso, 
para geradores de linguagens regulares?
...... (booleanos)  aL (string de LL
Reg
)
lFA revela modelo equivalente para geradores
 
A & C: Autômatos finitos 2
Modelos computacionais para LFs 
FA é um modelo para reconhecedores 
de linguagens regulares 
 aS* (string)  |d*(q
0
,a) F| (booleano de aL(M)?)
Como encontrar modelo computacional inverso, 
para geradores de linguagens regulares?
...... (booleanos)  aL (string de LL
Reg
)
lFA revela modelo equivalente para geradores
Input M output
 
A & C: Autômatos finitos 2
Modelos computacionais para LFs 
FA é um modelo para reconhecedores 
de linguagens regulares 
 aS* (string)  |d*(q
0
,a) F| (booleano de aL(M)?)
Como encontrar modelo computacional inverso, 
i.e., para geradores de linguagens regulares?
...... (booleanos)  aL (string de LL
Reg
)
lFA revela modelo equivalente para geradores
Input M output
 
A & C: Autômatos finitos 2
Modelos computacionais para LFs 
FA é um modelo para reconhecedores 
de linguagens regulares 
 aS* (string)  |d*(q
0
,a) F| (booleano de aL(M)?)
Como encontrar modelo computacional inverso, 
i.e., para geradores de linguagens regulares?
...... (booleanos)  aL (string de LL
Reg
)
lFA revela modelo equivalente para geradores
Input M output
Input M output
 
A & C: Autômatos finitos 2
Modelos computacionais para LFs 
FA é um modelo para reconhecedores 
de linguagens regulares 
 aS* (string)  |d*(q
0
,a) F| (booleano de aL(M)?)
Como encontrar modelo computacional inverso, 
i.e., para geradores de linguagens regulares?
...... (booleanos)  aL (string de LL
Reg
)
lFA revela modelo equivalente para geradores
Input M output
Input M output
 
A & C: Autômatos finitos 2
Equivalência funcional entre lFAs e NFAs 
Dado qualquer lFA M = (Q, , q
0
, d, F), existe
NFA M' que reconhece a mesma linguagem: 
M' = (2Q, , {q
0
}, d', F')
d' é dada pela tabela de transições de M e pelo
fecho reflexivo-transitivo de transições por l
T d'(V,a) = d(V,a)l
(estados alcançáveis a partir de V via 
transição por a + caminho rotulado por l)
 
A & C: Autômatos finitos 2
Equivalência funcional entre lFAs e NFAs 
Dado qualquer lFA M = (Q, , q
0
, d, F), existe
DFA M' que reconhece a mesma linguagem: 
M' = (2Q, , q'
0
, d', F')
d' é dada por transições de M com input e pelo 
fecho reflexivo-transitivo de transições por l
T d'(V,a) = d(V,a)l
(estados alcançáveis a partir de V via 
transição por a + caminho rotulado por l)
 
A & C: Autômatos finitos 2
Equivalência funcional entre lFAs e DFAs 
Dado qualquer lFA M = (Q, , q
0
, d, F), existe
DFA M' que reconhece a mesma linguagem: 
M' = (2Q, , q'
0
, d', F')
d' é dada por transições de M com input e pelo 
fecho reflexivo-transitivo de transições por l
T d'(V,a) = d(V,a)l
(estados alcançáveis a partir de V via 
transição por a + caminho rotulado por l)
 
A & C: Autômatos finitos 2
Demonstração de L(M
lFA
) = L(M
DFA
) 
Defina q'
0
={q
0
}l e os estados finais de M' por
F' = {VQ | VF} (V contém algum estado final de M)
Provaremos, por indução sobre |a|: 
d'*(q'
0
,a)  F'  d*(q
0
,a)F  
P(0): d'*(q'
0
,l) = {q'
0
} = {{q
0
}l} , e portanto
{q
0
}lF  d*(q
0
,l)F = {q
0
}lF  
 
A & C: Autômatos finitos 2
Demonstração de L(M
lFA
) = L(M
DFA
) 
Defina q'
0
={q
0
}l e os estados finais de M' por
F' = {VQ | VF} (V contém algum estado final de M)
Provaremos, por indução sobre |a|: 
d'*(q'
0
,a)  F'  d*(q
0
,a)F  
P(0): d'*(q'
0
,l) = {q'
0
} = {{q
0
}l} , e portanto
{q
0
}lF  d*(q
0
,l)F = {q
0
}lF  
 
A & C: Autômatos finitos 2
Demonstração de L(M
lFA
) = L(M
DFA
) 
Defina q'
0
={q
0
}l e os estados finais de M' por
F' = {VQ | VF} (V contém algum estado final de M)
Provaremos, por indução sobre |a|: 
d'*(q'
0
,a)  F'  d*(q
0
,a)F  
P(0): d'*(q'
0
,l) = {q'
0
} = {{q
0
}l} , e portanto
{q
0
}lF  d*(q
0
,l)F = {q
0
}lF  
def. comportamento DFA def. q inicial M'
 
A & C: Autômatos finitos 2
Demonstração de L(M
lFA
) = L(M
DFA
) 
Defina q'
0
={q
0
}l e os estados finais de M' por
F' = {VQ | VF} (V contém algum estado final de M)
Provaremos, por indução sobre |a|: 
d'*(q'
0
,a)  F'  d*(q
0
,a)F  
P(0): d'*(q'
0
,l) = {q'
0
} = {{q
0
}l} , e portanto
{q
0
}lF  d*(q
0
,l)F = {q
0
}lF  
def. comportamento DFA def. q inicial M'
 
A & C: Autômatos finitos 2
Demonstração de L(M
lFA
) = L(M
DFA
) 
Defina q'
0
={q
0
}l e os estados finais de M' por
F' = {VQ | VF} (V contém algum estado final de M)
Provaremos, por indução sobre |a|: 
d'*(q'
0
,a)  F'  d*(q
0
,a)F  
P(0): d'*(q'
0
,l) = {q'
0
} = {{q
0
}l} , e portanto
{q
0
}lF  d*(q
0
,l)F = {q
0
}lF  
def. comportamento DFA def. q inicial M'
M' reconhece l (aplicando definição de F') hipótese def. comportamento lFA
 
A & C: Autômatos finitos 2
Demonstração de L(M
lFA
) = L(M
DFA
) 
Defina q'
0
={q
0
}l e os estados finais de M' por
F' = {VQ | VF} (V contém algum estado final de M)
Provaremos, por indução sobre |a|: 
d'*(q'
0
,a)  F'  d*(q
0
,a)F  
P(0): d'*(q'
0
,l) = {q'
0
} = {{q
0
}l} , e portanto
{q
0
}lF  d*(q
0
,l)F   {q
0
}lF  
def.comportamento DFA def. q inicial M'
M' reconhece l Tese P(0) (aplicando definição de fecho) M reconhece l
 
A & C: Autômatos finitos 2
Demonstração de L(M
lFA
) = L(M
DFA
) 
Defina q'
0
={q
0
}l e os estados finais de M' por
F' = {VQ | VF} (V contém algum estado final de M)
Provaremos, por indução sobre |a|: 
d'*(q'
0
,a)  F'  d*(q
0
,a)F  
P(0): d'*(q'
0
,l) = {q'
0
} = {{q
0
}l} , e portanto
{q
0
}lF  d*(q
0
,l)F   {q
0
}lF  
def. comportamento DFA def. q inicial M'
M' reconhece l Hipótese P(0) def. comportamento lFA M reconhece l
 
A & C: Autômatos finitos 2
Demonstração de L(M
lFA
) = L(M
DFA
) 
Defina q'
0
={q
0
}l e os estados finais de M' por
F' = {VQ | VF} (V contém algum estado final de M)
Provaremos, por indução sobre |a|: 
d'*(q'
0
,a)  F'  d*(q
0
,a)F  
P(0): d'*(q'
0
,l) = {q'
0
} = {{q
0
}l} , e portanto
{q
0
}lF  d*(q
0
,l)F   {q
0
}lF  
def. comportamento DFA def. q inicial M'
M' reconhece l Hipótese P(0). def. comportamento lFA M reconhece l
 
A & C: Autômatos finitos 2
Demonstração de L(M
lFA
) = L(M
DFA
) (continuação)
nN [ P(n)  P(n+1) ]: (supondo aL(M')aL(M),
Dado V = d'*(q'
0
,|a|=n), temos: aS* [qV 
 caminho de q
0
 a q em M cuja concatenação 
de rótulos produz a]. Prova por indução, dado que:
T = d'*(q'
0
,aa) = d'(d'*(q'
0
,a),a) = d(V,a)l
em particular aaL(M')   caminho de q
0
 a 
qF em M c.c.r.p. aa  aaL(M) 
 
A & C: Autômatos finitos 2
Demonstração de L(M
lFA
) = L(M
DFA
) (continuação)
nN [ P(n)  P(n+1) ]: (supondo aL(M')aL(M))
Dado V = d'*(q'
0
,a), temos: aS* [qV 
 caminho de q
0
 a q em M cuja concatenação 
de rótulos produz a]. Prova por indução, dado que:
T = d'*(q'
0
,aa) = d'(d'*(q'
0
,a),a) = d(V,a)l
em particular aaL(M')   caminho de q
0
 a 
qF em M c.c.r.p. aa  aaL(M) 
 
A & C: Autômatos finitos 2
Demonstração de L(M
lFA
) = L(M
DFA
) (continuação)
nN [ P(n)  P(n+1) ]: (supondo aL(M')aL(M))
Dado V = d'*(q'
0
,a), temos: aS* [qV 
 caminho de q
0
 a q em M cuja concatenação 
de rótulos produz a]. Prova por indução, dado que:
d'*(q'
0
,aa) = d'(d'*(q'
0
,a),a) = d(V,a)l
em particular aaL(M')   caminho de q
0
 a 
qF em M c.c.r.p. aa  aaL(M) 
 
A & C: Autômatos finitos 2
Demonstração de L(M
lFA
) = L(M
DFA
) (continuação)
nN [ P(n)  P(n+1) ]: (supondo aL(M')aL(M))
Dado V = d'*(q'
0
,a), temos: aS* [qV 
 caminho de q
0
 a q em M cuja concatenação 
de rótulos produz a]. Prova por indução, dado que:
d'*(q'
0
,aa) = d'(d'*(q'
0
,a),a) = d(V,a)l
em particular aaL(M')   caminho de q
0
 a 
qF em M c.c.r.p. aa  aaL(M) 
 
A & C: Autômatos finitos 2
Demonstração de L(M
lFA
) = L(M
DFA
) (continuação)
nN [ P(n)  P(n+1) ]: (supondo aL(M')aL(M))
Dado V = d'*(q'
0
,a), temos: aS* [qV 
 caminho de q
0
 a q em M cuja concatenação 
de rótulos produz a]. Prova por indução, dado que:
d'*(q'
0
,aa) = d'(d'*(q'
0
,a),a) = d(V,a)l
em particular, aaL(M')   caminho em M de
q
0
 a qF que se concatena em aa  aaL(M) 
 
A & C: Autômatos finitos 2
Demonstração de L(M
lFA
) = L(M
DFA
) (continuação)
nN [ P(n)  P(n+1) ]: (supondo aL(M')aL(M))
Dado V = d'*(q'
0
,a), temos: aS* [qV 
 caminho de q
0
 a q em M cuja concatenação 
de rótulos produz a]. Prova por indução, dado que:
d'*(q'
0
,aa) = d'(d'*(q'
0
,a),a) = d(V,a)l
em particular, aaL(M')   caminho em M de
q
0
 a qF que se concatena em aa  aaL(M) 
 
A & C: Autômatos finitos 2
Demonstração de L(M
lFA
) = L(M
DFA
) (continuação)
nN [ P(n)  P(n+1) ]: (supondo aL(M')aL(M))
Dado V = d'*(q'
0
,a), temos: aS* [qV 
 caminho de q
0
 a q em M cuja concatenação 
de rótulos produz a]. Prova por indução, dado que:
d'*(q'
0
,aa) = d'(d'*(q'
0
,a),a) = d(V,a)l
em particular, aaL(M')   caminho em M de
q
0
 a qF que se concatena em aa  aaL(M)