Exercício 04.13

Desenvolva um Autômato Finito com Movimentos Vazios (AFε) sobre o alfabeto Σ = {a, b, c, d}, que reconheça a linguagem L = {w | w possui ab ou bcda ou bca como prefixo, dab ou acab ou cad como subpalavra e dad ou aba ou bbc 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, q22, q23, q24, q25, q26, q27, q28, q29, q30, q31, q32, q33, q34, q35, q36, q37, q38, q39, q40}, δ, q0, {q40})

δ a b c d ε
q0 - - - - {q1, q4, q9}
q1 {q2} - - - -
q2 - {q3} - - -
q3 - - - - {q13}
q4 - {q5} - - -
q5 - - {q6} - -
q6 - - - {q7} -
q7 {q8} - - - -
q8 - - - - {q13, q16, q19}
q9 - {q10} - - -
q10 - - {q11} - -
q11 {q12} - - - -
q12 - - - - {q13, q19, q25}
q13 {q13} {q13} {q13} {q13} {q14, q18, q23}
q14 - - - {q15} -
q15 {q16} - - - -
q16 - {q17} - - -
q17 - - - - {q27, q34, q37}
q18 {q19} - - - -
q19 - - {q20} - -
q20 {q21} - - - -
q21 - {q22} - - -
q22 - - - - {q27, q34, q37}
q23 - - {q24} - -
q24 {q25} - - - -
q25 - - - {q26} -
q26 - - - - {q27, q29}
q27 {q27} {q27} {q27} {q27} {q28, q32, q36}
q28 - - - {q29} -
q29 {q30} - - - -
q30 - - - {q31} -
q31 - - - - {q40}
q32 {q33} - - - -
q33 - {q34} - - -
q34 {q35} - - - -
q35 - - - - {q40}
q36 - {q37} - - -
q37 - {q38} - - -
q38 - - {q39} - -
q39 - - - - {q40}
q40 - - - - -

Recomendamos

Kinghost Copy Duolingo