Exercício 06.15

Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão (a+b)*(aa+bb)(a+b)*. Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados.


Autômato Finito com Movimentos Vazios (AFε)

M = ({a, b}, {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11, q12, q13, q14, q15, q16, q17, q18, q19, q20, q21, q22, q23, q24, q25, q26, q27, q28, q29, q30, q31}, δ, q0, {q31})

Grafo com a função de transição de M
δ a b ε
q0 - - {q1}
q1 - - {q2, q10}
q2 - - {q3}
q3 - - {q4, q6}
q4 {q5} - -
q5 - - {q8}
q6 - {q7} -
q7 - - {q8}
q8 - - {q9}
q9 - - {q2, q10}
q10 - - {q11}
q11 - - {q12, q16}
q12 {q13} - -
q13 - - {q14}
q14 {q15} - -
q15 - - {q20}
q16 - {q17} -
q17 - - {q18}
q18 - {q19} -
q19 - - {q20}
q20 - - {q21}
q21 - - {q22, q30}
q22 - - {q23}
q23 - - {q24, q26}
q24 {q25} - -
q25 - - {q28}
q26 - {q27} -
q27 - - {q28}
q28 - - {q29}
q29 - - {q22, q30}
q30 - - {q31}
q31 - - -

Autômato Finito Determinístico (AFD)

M = ({a, b}, {s0, s1, s2, s3, s4, s5, s6, s7, s8}, δ, s0, {s3, s4, s5, s6, s7, s8})

Grafo com a função de transição de M
δ a b
s0 s1 s2
s1 s3 s2
s2 s1 s4
s3 s5 s6
s4 s7 s8
s5 s5 s6
s6 s7 s8
s7 s5 s6
s8 s7 s8

Autômato Finito Determinístico (AFD) Simplificado

M = ({a, b}, {C0, C1, C2, C3}, δ, C1, {C0})

Grafo com a função de transição de M
δ a b
C0 C0 C0
C1 C2 C3
C2 C0 C3
C3 C2 C0

Recomendamos

Revista Tema Revista FOSSGIS Brasil Duolingo