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

Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão (a + b)*(ab + bc). Utilize os procedimentos formais para obter o Autômato Finito com Movimentos Vazios (AFε), convertê-lo para um Autômato Finito Determinístico (AFD) e minimizar seu número de estados.

 

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

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

M = ({a, b, c}, {q0, q1, q2, q3, q4}, δ, q0, {q3, q4})

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
q0q1q2-
q1q1q3-
q2q1q2q4
q3q1q2q4
q4---

M = ({a, b, c}, {q0, q1, q2, q3, q4}, δ, q0, {q3, q4})

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
δab
q0q1q2-
q1q1q3-
q2q1q2q4
q3q1q2q4
q4---