Exercício 03.40

Desenvolva um Autômato Finito Não-Determinístico (AFN) sobre o alfabeto Σ = {1, 2, 3, 4}, que reconheça a linguagem L = {w | w possui 234 ou 341 ou 411 como prefixo, 132 ou 412 ou 423 como subpalavra e 121 ou 213 ou 342 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}, δ, q0, {q21})

δ 1 2 3 4
q0 - {q1} {q3} {q5}
q1 - - {q2} -
q2 - - - {q7, q10, q12}
q3 - - - {q4}
q4 {q7, q8, q11} - - -
q5 {q6} - - -
q6 {q7, q8} - - -
q7 {q7, q8} {q7} {q7} {q7, q10, q12}
q8 - - {q9} -
q9 - {q14, q17} - -
q10 {q11} - - -
q11 - {q14, q16, q17} - -
q12 - {q13} - -
q13 - - {q14, q19} -
q14 {q14, q15} {q14, q17} {q14, q19} {q14}
q15 - {q16} - -
q16 {q21} - - -
q17 {q18} - - -
q18 - - {q21} -
q19 - - - {q20}
q20 - {q21} - -
q21 - - - -

Recomendamos

Copy Revista LibreOffice Magazine Java Magazine