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.45

Exercício 04.45

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 1214 ou 2443 ou 3424 como prefixo, 141 ou 3114 ou 4324 como subpalavra e 1323 ou 243 ou 411 como sufixo}.

Solução do Exercício

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

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

Ybadoo   •   Copyright 2009/2026   •   GFDL