Exercício 03.12

Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {a, b, c, d}, que reconheça a linguagem L = {w | w possui bab ou dac ou ba como prefixo, abb ou cac ou acbc como subpalavra e bca ou acd ou cda como sufixo}.


Resposta

M = ({a, b, c, d}, {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11, q12, q13, q14, q15, q16, q17, q18, q19, q20, q21}, δ, q0, {q21})

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

Recomendamos

Clique Alimentos Vida de Programador Revista Segurança Digital