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 xx(x + y + z)*yy. 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 = ({x, y, z}, {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
δxyzε
q0---{q1}
q1{q2}---
q2---{q3}
q3{q4}---
q4---{q5}
q5---{q6, q16}
q6---{q7}
q7---{q8, q10, q12}
q8{q9}---
q9---{q14}
q10-{q11}--
q11---{q14}
q12--{q13}-
q13---{q14}
q14---{q15}
q15---{q6, q16}
q16---{q17}
q17-{q18}--
q18---{q19}
q19-{q20}--
q20---{q21}
q21----

M = ({x, y, z}, {q0, q1, q2, q3, q4, q5, q6}, δ, q0, {q6})

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
δxyz
q0q1--
q1q2--
q2q3q4q5
q3q3q4q5
q4q3q6q5
q5q3q4q5
q6q3q6q5

M = ({x, y, z}, {q0, q1, q2, q3, q4}, δ, q0, {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
δxyz
q0q1--
q1q2--
q2q2q3q2
q3q2q4q2
q4q2q4q2