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

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 bcbc ou dabc ou dada como prefixo, aabc ou bcda ou ccad ou dacb como subpalavra e aada ou acbd ou bccc ou ddab como sufixo}.

 

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, q41, q42, q43, q44, q45, q46, q47, q48, q49, q50}, δ, q0, {q50})

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
δabcdε
q0----{q1}
q1-{q2}-{q6, q10}-
q2--{q3}--
q3-{q4}---
q4--{q5}--
q5----{q14, q21, q24}
q6{q7}----
q7-{q8}---
q8--{q9}--
q9----{q14, q21, q24}
q10{q11}----
q11---{q12}-
q12{q13}----
q13----{q14, q16, q29}
q14{q14}{q14}{q14}{q14}{q15}
q15{q16}{q20}{q24}{q28}-
q16{q17}----
q17-{q18}---
q18--{q19}--
q19----{q32, q43}
q20--{q21}--
q21---{q22}-
q22{q23}----
q23----{q32, q34, q38}
q24--{q25}--
q25{q26}----
q26---{q27}-
q27----{q32, q46}
q28{q29}----
q29--{q30}--
q30-{q31}---
q31----{q32, q40, q42}
q32{q32}{q32}{q32}{q32}{q33}
q33{q34, q38}{q42}-{q46}-
q34{q35}----
q35---{q36}-
q36{q37}----
q37----{q50}
q38--{q39}--
q39-{q40}---
q40---{q41}-
q41----{q50}
q42--{q43}--
q43--{q44}--
q44--{q45}--
q45----{q50}
q46---{q47}-
q47{q48}----
q48-{q49}---
q49----{q50}
q50-----