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

  1. Ybadoo
  2. Tutoriais
  3. Linguagens Formais e Autômatos
  4. Autômatos Finitos com Movimentos Vazios
  5. Exercício 04.38

Exercício 04.38

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 1142 ou 4141 ou 4231 como prefixo, 14343 ou 41221 ou 42214 como subpalavra e 141 ou 211 ou 432 como sufixo}.

 

Solução do Exercício

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

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

Ybadoo   •   Copyright 2009/2025   •   GFDL