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}, que reconheça a linguagem L = {w | w possui acb ou bca ou cac como prefixo, bab ou bba ou bcc como subpalavra e cac ou cbb ou cbc como sufixo}.

 

M = ({a, b, c}, {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}, δ, q0, {q33})

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
δabcε
q0---{q1}
q1{q2}{q5}{q8}-
q2--{q3}-
q3-{q4}--
q4---{q11, q13, q16, q19}
q5--{q6}-
q6{q7}---
q7---{q11}
q8{q9}---
q9--{q10}-
q10---{q11}
q11{q11}{q11}{q11}{q12}
q12-{q13, q16, q19}--
q13{q14}---
q14-{q15}--
q15---{q22}
q16-{q17}--
q17{q18}---
q18---{q22}
q19--{q20}-
q20--{q21}-
q21---{q22, q24, q27, q30}
q22{q22}{q22}{q22}{q23}
q23--{q24, q27, q30}-
q24{q25}---
q25--{q26}-
q26---{q33}
q27-{q28}--
q28-{q29}--
q29---{q33}
q30-{q31}--
q31--{q32}-
q32---{q33}
q33----