Exercício 06.10

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)*(b + c)*bc. 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, q20, q21, q22, q23}, δ, q0, {q23})

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

Autômato Finito Determinístico (AFD)

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

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

Autômato Finito Determinístico (AFD) Simplificado

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

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

Recomendamos

Copy Um Sábado Qualquer Agenda TI