Exercício 06.06

Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão (xx)*(y + z)z*. 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 = ({x, y, z}, {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11, q12, q13, q14, q15, q16, q17, q18, q19, q20}, δ, q0, {q20})

δ x y z ε
q0 - - - {q1}
q1 - - - {q2, q7}
q2 - - - {q3}
q3 {q4} - - -
q4 {q5} - - -
q5 - - - {q6}
q6 - - - {q2, q7}
q7 - - - {q8}
q8 - - - {q9, q11}
q9 - {q10} - -
q10 - - - {q13}
q11 - - {q12} -
q12 - - - {q13}
q13 - - - {q14}
q14 - - - {q15, q19}
q15 - - - {q16}
q16 - - {q17} -
q17 - - - {q18}
q18 - - - {q15, q19}
q19 - - - {q20}
q20 - - - -

Autômato Finito Determinístico (AFD)

M = ({x, y, z}, {s0, s1, s2, s3, s4, s5}, δ, s0, {s2, s3, s5})

δ x y z
s0 s1 s2 s3
s1 s4 - -
s2 - - s5
s3 - - s5
s4 s1 s2 s3
s5 - - s5

Autômato Finito Determinístico (AFD) Simplificado

M = ({x, y, z}, {C0, C1, C2}, δ, C2, {C0})

δ x y z
C0 - - C0
C1 C2 - -
C2 C1 C0 C0


Recomendamos

Revista FOSSGIS Brasil Revista LibreOffice Magazine Vida de Suporte