Ybadoo - Soluções em Software Livre
Tutoriais
Linguagens Formais e Autômatos

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 124 ou 323 ou 432 como prefixo, 233 ou 2434 ou 424 como subpalavra e 241 ou 342 ou 412 como sufixo}.

 

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}, δ, q0, {q40})

Grafo com a função de transição de M
Grafo com a função de transição de M
Tabela com a função de transição de M
δ1234ε
q0----{q1, q5, q9}
q1{q2}----
q2-{q3}---
q3---{q4}-
q4----{q13, q20, q24}
q5--{q6}--
q6-{q7}---
q7--{q8}--
q8----{q13, q16}
q9---{q10}-
q10--{q11}--
q11-{q12}---
q12----{q13, q15, q19}
q13{q13}{q13}{q13}{q13}{q14, q18, q23}
q14-{q15}---
q15--{q16}--
q16--{q17}--
q17----{q27, q33}
q18-{q19}---
q19---{q20}-
q20--{q21}--
q21---{q22}-
q22----{q27, q34, q37}
q23---{q24}-
q24-{q25}---
q25---{q26}-
q26----{q27, q30, q37}
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-----