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

Desenvolva um Autômato Finito Não-Determinístico (AFN) 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}, δ, q0, {q16})

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}{q3}{q5}
q1--{q2}
q2-{q7, q8}-
q3--{q4}
q4{q7}--
q5{q6}--
q6--{q7}
q7{q7}{q7, q8}{q7}
q8{q9}{q10}{q11}
q9-{q12}-
q10{q12}--
q11--{q12, q13}
q12{q12}{q12}{q12, q13}
q13{q14}{q15}-
q14--{q16}
q15-{q16}{q16}
q16---