Exercício 06.17

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 + c)c*. 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, c}, {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11, q12, q13, q14, q15, q16, q17, q18, q19}, δ, q0, {q19})

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

Autômato Finito Determinístico (AFD)

M = ({a, b, c}, {q0, q1, q2, q3, q4}, δ, q0, {q3, q4})

δ a b c
q0 q1 q2 -
q1 - q3 q4
q2 - q3 q4
q3 - q3 q4
q4 - - -

Autômato Finito Determinístico (AFD) Simplificado

M = ({a, b, c}, {q0, q1, q2, q3}, δ, q0, {q2, q3})

δ a b c
q0 q1 q1 -
q1 - q2 q3
q2 - q2 q3
q3 - - -

Recomendamos

Revista Digital Revista FOSSGIS Brasil Revista Tema