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

Exercício 06.29

Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão aa(a + b + c)*bb(a + b + c)*cc. 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.

Solução do Exercício

Algoritmo de Thompson

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, q22, q23, q24, q25, q26, q27, q28, q29, q30, q31, q32, q33, q34, q35, q36, q37}, δ, q0, {q37})

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}---
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---{q22, q32}
q22---{q23}
q23---{q24, q26, q28}
q24{q25}---
q25---{q30}
q26-{q27}--
q27---{q30}
q28--{q29}-
q29---{q30}
q30---{q31}
q31---{q22, q32}
q32---{q33}
q33--{q34}-
q34---{q35}
q35--{q36}-
q36---{q37}
q37----

Método da Construção de Subconjuntos

ε*{q0} = {q0, q1} → (s0)

Estado s0
ε*{q0} = {q0, q1} → (s0)

ε*{q2} = {q2, q3} → (s1)

Estado s1
ε*{q2} = {q2, q3} → (s1)

ε*{q4} = {q4, q5, q6, q7, q8, q10, q12, q16, q17} → (s2)

Estado s2
ε*{q4} = {q4, q5, q6, q7, q8, q10, q12, q16, q17} → (s2)

ε*{q9} = {q6, q7, q8, q9, q10, q12, q14, q15, q16, q17} → (s3)

Estado s3
ε*{q9} = {q6, q7, q8, q9, q10, q12, q14, q15, q16, q17} → (s3)

ε*{q11, q18} = {q6, q7, q8, q10, q11, q12, q14, q15, q16, q17, q18, q19} → (s4)

Estado s4
ε*{q11, q18} = {q6, q7, q8, q10, q11, q12, q14, q15, q16, q17, q18, q19} → (s4)

ε*{q13} = {q6, q7, q8, q10, q12, q13, q14, q15, q16, q17} → (s5)

Estado s5
ε*{q13} = {q6, q7, q8, q10, q12, q13, q14, q15, q16, q17} → (s5)

ε*{q11, q18, q20} = {q6, q7, q8, q10, q11, q12, q14, q15, q16, q17, q18, q19, q20, q21, q22, q23, q24, q26, q28, q32, q33} → (s6)

Estado s6
ε*{q11, q18, q20} = {q6, q7, q8, q10, q11, q12, q14, q15, q16, q17, q18, q19, q20, q21, q22, q23, q24, q26, q28, q32, q33} → (s6)

ε*{q9, q25} = {q6, q7, q8, q9, q10, q12, q14, q15, q16, q17, q22, q23, q24, q25, q26, q28, q30, q31, q32, q33} → (s7)

Estado s7
ε*{q9, q25} = {q6, q7, q8, q9, q10, q12, q14, q15, q16, q17, q22, q23, q24, q25, q26, q28, q30, q31, q32, q33} → (s7)

ε*{q11, q18, q20, q27} = {q6, q7, q8, q10, q11, q12, q14, q15, q16, q17, q18, q19, q20, q21, q22, q23, q24, q26, q27, q28, q30, q31, q32, q33} → (s8)

Estado s8
ε*{q11, q18, q20, q27} = {q6, q7, q8, q10, q11, q12, q14, q15, q16, q17, q18, q19, q20, q21, q22, q23, q24, q26, q27, q28, q30, q31, q32, q33} → (s8)

ε*{q13, q29, q34} = {q6, q7, q8, q10, q12, q13, q14, q15, q16, q17, q22, q23, q24, q26, q28, q29, q30, q31, q32, q33, q34, q35} → (s9)

Estado s9
ε*{q13, q29, q34} = {q6, q7, q8, q10, q12, q13, q14, q15, q16, q17, q22, q23, q24, q26, q28, q29, q30, q31, q32, q33, q34, q35} → (s9)

ε*{q11, q18, q27} = {q6, q7, q8, q10, q11, q12, q14, q15, q16, q17, q18, q19, q22, q23, q24, q26, q27, q28, q30, q31, q32, q33} → (s10)

Estado s10
ε*{q11, q18, q27} = {q6, q7, q8, q10, q11, q12, q14, q15, q16, q17, q18, q19, q22, q23, q24, q26, q27, q28, q30, q31, q32, q33} → (s10)

ε*{q13, q29, q34, q36} = {q6, q7, q8, q10, q12, q13, q14, q15, q16, q17, q22, q23, q24, q26, q28, q29, q30, q31, q32, q33, q34, q35, q36, q37} → (s11)

Estado s11
ε*{q13, q29, q34, q36} = {q6, q7, q8, q10, q12, q13, q14, q15, q16, q17, q22, q23, q24, q26, q28, q29, q30, q31, q32, q33, q34, q35, q36, q37} → (s11)

M = ({a, b, c}, {s0, s1, s2, s3, s4, s5, s6, s7, s8, s9, s10, s11}, δ, s0, {s11})

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
s0s1--
s1s2--
s2s3s4s5
s3s3s4s5
s4s3s6s5
s5s3s4s5
s6s7s8s9
s7s7s10s9
s8s7s8s9
s9s7s10s11
s10s7s8s9
s11s7s10s11

Minimização de Estados do Autômato

P1 = {C0, C1}, com C0 = {s11} e C1 = {s0, s1, s2, s3, s4, s5, s6, s7, s8, s9, s10}

Partição 01
P1 = {C0, C1}, com C0 = {s11} e C2 = {s0, s1, s2, s3, s4, s5, s6, s7, s8, s9, s10}

P2 = {C0, C1, C2}, com C0 = {s11}, C1 = {s0} e C2 = {s1, s2, s3, s4, s5, s6, s7, s8, s9, s10}

Partição 02
P2 = {C0, C1, C2}, com C0 = {s11}, C1 = {s0} e C2 = {s1, s2, s3, s4, s5, s6, s7, s8, s9, s10}

P3 = {C0, C1, C2, C3}, com C0 = {s11}, C1 = {s0}, C2 = {s1} e C3 = {s2, s3, s4, s5, s6, s7, s8, s9, s10}

Partição 03
P3 = {C0, C1, C2, C3}, com C0 = {s11}, C1 = {s0}, C2 = {s1} e C3 = {s2, s3, s4, s5, s6, s7, s8, s9, s10}

P4 = {C0, C1, C2, C3, C4}, com C0 = {s11}, C1 = {s0}, C2 = {s1}, C3 = {s9} e C4 = {s2, s3, s4, s5, s6, s7, s8, s10}

Partição 04
P4 = {C0, C1, C2, C3, C4}, com C0 = {s11}, C1 = {s0}, C2 = {s1}, C3 = {s9} e C4 = {s2, s3, s4, s5, s6, s7, s8, s10}

P5 = {C0, C1, C2, C3, C4, C5}, com C0 = {s11}, C1 = {s0}, C2 = {s1}, C3 = {s9}, C4 = {s2, s3, s4, s5} e C5 = {s6, s7, s8, s10}

Partição 05
P5 = {C0, C1, C2, C3, C4, C5}, com C0 = {s11}, C1 = {s0}, C2 = {s1}, C3 = {s9}, C4 = {s2, s3, s4, s5} e C5 = {s6, s7, s8, s10}

P6 = {C0, C1, C2, C3, C4, C5, C6}, com C0 = {s11}, C1 = {s0}, C2 = {s1}, C3 = {s9}, C4 = {s4}, C5 = {s2, s3, s5} e C6 = {s6, s7, s8, s10}

Partição 06
P6 = {C0, C1, C2, C3, C4, C5, C6}, com C0 = {s11}, C1 = {s0}, C2 = {s1}, C3 = {s9}, C4 = {s4}, C5 = {s2, s3, s5} e C6 = {s6, s7, s8, s10}

M = ({a, b, c}, {C0, C1, C2, C3, C4, C5, C6}, δ, 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
δabc
C0C6C6C0
C1C2--
C2C5--
C3C6C6C0
C4C5C6C5
C5C5C4C5
C6C6C6C3

Ybadoo   •   Copyright 2009/2026   •   GFDL