Resolução lfa

ATIVIDADE EXTRA-CLASSE
4 – Conversão AFε RESOLUÇÃO AFND

1-) Fε(A) = {A, B} ε Fε(B) = {B} ε Fε(C) = {A, B, C} ε C

b a) A

a,b a,b b b b b a,b

b

B

b) a a,b a,b a,b a,b q2 q3 a,b b Fε(q1) = {q1, q2, q3, q4} ε Fε(q2) = {q2, q3, q4} ε Fε(q3) = {q3, q4} ε Fε(q4) = {q4} ε

q1

q4

a,b

a,b

a,b c) a,b q0 a,b a,b q1 b a,b a q2 a,b q3 Fε(q0) = {q0, q1} ε Fε(q1) = {q1} ε Fε(q2) = {q2, q3} ε ε Fε(q3) = {q3}

b a

d-)

a,b q0 a a,b a q1

a,b a,b a q2

a,b

Fε(q0) = {q0, q1} ε Fε(q1) = {q1} ε Fε(q2) = {q1, q2} ε

e-) 0,1 A B 0,1 C Fε(A) = {A, B} ε Fε(B) = {B} ε Fε(C) = {C} ε

f-) A

0,1 0,1

B

0,1 0,1

C

Fε(A) = {A, C} ε Fε(B) = {B} ε Fε(C) = {A, C} ε

g-) a a,b q0 a,b q2 a q1 a a,b a,b a q3 a,b Fε(q0) = {q0, q1} ε Fε(q1) = {q1} ε Fε(q2) = {q2, q3} ε Fε(q3) = {q3} ε

a,b h-) a,b 0 a a a a 2 b 3 a,b Fε(0) = {0} ε Fε(1) = {1, 2} ε ε Fε(2) = {2} Fε(3) = {3} ε

1 a

b

2-) De AFε ε AFND Fε(q0) = {q0} ε Fε(q1) = {q1} ε Fε(q2) = {q1, q2, q3} ε Fε(q3) = {q1, q3} ε

a a,b q0 a,b q2 q1

a,b a,b q3 a,b a a,b

a,b

De AFND

AFD

a a,b a b < q1q2q3> a < q0q1q2q3> a b b < q1q3> P b R a Q b b S a a,b

Minimização de AFD Q a,b R S P Q R PQRS