Exercício 04.19

Desenvolva um Autômato Finito com Movimentos Vazios (AFε) sobre o alfabeto Σ = {1, 2, 3, 4}, que reconheça a linguagem L = {w | w possui 1234 ou 1212 ou 3434 como prefixo, 3412 ou 4421 ou 1243 ou 2234 como subpalavra e 2212 ou 1123 ou 2431 ou 3444 como sufixo}.


Resposta

M = ({1, 2, 3, 4}, {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, q41, q42, q43, q44, q45, q46, q47, q48, q49, q50, q51, q52, q53, q54, q55, q56, q57, q58}, δ, q0, {q58})

δ 1 2 3 4 ε
q0 - - - - {q1, q6, q11}
q1 {q2} - - - -
q2 - {q3} - - -
q3 - - {q4} - -
q4 - - - {q5} -
q5 - - - - {q16, q19, q23}
q6 {q7} - - - -
q7 - {q8} - - -
q8 {q9} - - - -
q9 - {q10} - - -
q10 - - - - {q16, q29, q33}
q11 - - {q12} - -
q12 - - - {q13} -
q13 - - {q14} - -
q14 - - - {q15} -
q15 - - - - {q16, q19, q23}
q16 {q16} {q16} {q16} {q16} {q17, q22, q27, q32}
q17 - - {q18} - -
q18 - - - {q19} -
q19 {q20} - - - -
q20 - {q21} - - -
q21 - - - - {q37, q39, q49}
q22 - - - {q23} -
q23 - - - {q24} -
q24 - {q25} - - -
q25 {q26} - - - -
q26 - - - - {q37, q44}
q27 {q28} - - - -
q28 - {q29} - - -
q29 - - - {q30} -
q30 - - {q31} - -
q31 - - - - {q37, q51, q54}
q32 - {q33} - - -
q33 - {q34} - - -
q34 - - {q35} - -
q35 - - - {q36} -
q36 - - - - {q37, q55}
q37 {q37} {q37} {q37} {q37} {q38, q43, q48, q53}
q38 - {q39} - - -
q39 - {q40} - - -
q40 {q41} - - - -
q41 - {q42} - - -
q42 - - - - {q58}
q43 {q44} - - - -
q44 {q45} - - - -
q45 - {q46} - - -
q46 - - {q47} - -
q47 - - - - {q58}
q48 - {q49} - - -
q49 - - - {q50} -
q50 - - {q51} - -
q51 {q52} - - - -
q52 - - - - {q58}
q53 - - {q54} - -
q54 - - - {q55} -
q55 - - - {q56} -
q56 - - - {q57} -
q57 - - - - {q58}
q58 - - - - -

Recomendamos

Revista Tema Kinghost Revista Digital