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 (a + b)* b (a + b)* a. 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}, {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}, δ, q0, {q27})

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

M = ({a, b}, {s0, s1, s2, s3, s4, s5}, δ, s0, {s4})

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
s0s1-
s1s2s3
s2s2s3
s3s4s5
s4s4s5
s5s4s5

M = ({a, b}, {C0, C1, C2, C3}, δ, C1, {C0})

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
C0C0C3
C1C2-
C2C2C3
C3C0C3