(q2 , p0 )
(q2 , p1 )
(q1 , p0 )
(q1 , p1 )
− F2 = {(q1 , p1 )}
(q2 , p1 )
(q2 , p1 )
− F2 =a {(q
1 , p1 )}
Caracterize
linguagem
LD .
Caracterize
a linguagem
LDa. partir de dois autómatos finitos de(c) Proponha
um algoritmo
que
(c) Proponha
queum
a partir
de dois
autómatos
finitosD
de-tal
terministas
D1um
e Dalgoritmo
autómato
finito
determinista
2 construa
terministas
D e D construa um autómato finito determinista D tal
que L
D = LD1 ∩ 1LD2 .2
que L = LD1 ∩ LD2 .
Nota: em D
certas situações o algoritmo poderá não construir o autómato
Nota: em certas situações o algoritmo poderá não construir o autómato
mais simples para LD = LD1 ∩ LD2 .
mais simples para LD = LD1 ∩ LD2 .
21. Proponha
um um
algoritmo
queque
a apartir
finitosdeterdeter21. Proponha
algoritmo
partirdededois
dois autómatos
autómatos finitos
ministas
D1 eDD
construa
um autómato finito determinista D tal que
2 D
ministas
1 e
2 construa um autómato finito determinista D tal que
LD =LL
∪DL1 D∪2L
. D2 .
1 L
DD=
TPC
66
Sabemos que se um a.f.d. D1 reconhece uma linguagem
LD1 e um a.f.d. D2 reconhece uma linguagem LD2 então a
linguagem reconhecida pelo autómato D = D1 × D2 é a
linguagem L = LD1 ∩ LD2 (Assumamos que os alfabetos de
D1 e D2 são idênticos). Assim sendo, um algoritmo para a
tarefa em questão, dado como input os dois autómatos
(1)
(2)
D1 = (Q1 , I, δ1 , q0 , F1 ) e D2 = (Q2 , I, δ2 , q0 , F2 ) ,
constroi um autómato D = (Q, I, δ, q0 , F ) , em que
1. Q é o conjunto dos pares (q1 , q2 ) com q1 ∈ Q1 , q2 ∈ Q2 ;
2. A função de transição δ é dada por
δ((q1 , q2 ), σ) = (q1! , q2! )
sempre que δ1 (q1 , σ) = q1! e δ2 (q2 , σ) = q2! ;
3. q0 = (q0(1) , q0(2) ) ; e
4. F = {(q1 , q2 ) : q1 ∈ F1 , q2 ∈ F2 } .