Exercício 06.05

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(ab)*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 (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}, δ, q0, {q12})

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

Autômato Finito Determinístico (AFD)

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

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

Autômato Finito Determinístico (AFD) Simplificado

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

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


Recomendamos

Duolingo Revista LibreOffice Magazine Agenda TI