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

  1. Ybadoo
  2. Tutoriais
  3. Linguagens Formais e Autômatos
  4. Conversão de Expressões Regulares (ER) para Autômatos Finitos Determinísticos (AFD)
  5. Exercício 06.27

Exercício 06.27

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.

 

Autômato Finito com Movimentos Vazios (AFε)

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---

Autômato Finito Determinístico (AFD)

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

Autômato Finito Determinístico (AFD) Simplificado

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

Ybadoo   •   Copyright 2009/2025   •   GFDL