Exercício 06.11

Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão (ab)*(ba)*. 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 (Ricarte, 2008).


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}, δ, q0, {q17})

δ a b ε
q0 - - {q1}
q1 - - {q2, q8}
q2 - - {q3}
q3 {q4} - -
q4 - - {q5}
q5 - {q6} -
q6 - - {q7}
q7 - - {q2, q8}
q8 - - {q9}
q9 - - {q10, q16}
q10 - - {q11}
q11 - {q12} -
q12 - - {q13}
q13 {q14} - -
q14 - - {q15}
q15 - - {q10, q16}
q16 - - {q17}
q16 - - -

Autômato Finito Determinístico (AFD)

M = ({a, b}, {s0, s1, s2, s3, s4}, δ, s0, {s0, s3, s4})

δ a b
s0 s1 s2
s1 - s3
s2 s4 -
s3 s1 s2
s4 - s2

Autômato Finito Determinístico (AFD) Simplificado

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

δ a b
C0 - C3
C1 C2 C3
C2 - C1
C3 C0 -

Recomendamos

Agenda TI Clique Alimentos Java Magazine