Exercício 04.14

Desenvolva um Autômato Finito com Movimentos Vazios (AFε) sobre o alfabeto Σ = {i, j, k}, que reconheça a linguagem L = {w | w possui iik ou kji ou jkj como prefixo, kjji ou jiik ou ikki como subpalavra e ikk ou jii ou kkj como sufixo}.


Resposta

M = ({i, j, k}, {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}, δ, q0, {q42})

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

Recomendamos

Vida de Suporte Revista Digital Vida de Programador