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

Exercício 06.23

Desenvolva um Autômato Finito Determinístico (AFD) com um número mínimo de estados para reconhecer sentenças descritas pela expressão (c + ε)(a + b)*c. 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, c}, {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11, q12, q13, q14, q15, q16, q17, q18, q19}, δ, q0, {q19})

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

Autômato Finito Determinístico (AFD)

M = ({a, b, c}, {q0, q1, q2, q3, q4}, δ, q0, {q2, 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
q0q1q3q2
q1q1q3q4
q2q1q3q4
q3q1q3q4
q4---

Autômato Finito Determinístico (AFD) Simplificado

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

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
q0q1q1q2
q1q1q1q3
q2q1q1q3
q3---

Ybadoo   •   Copyright 2009/2024   •   GFDL