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

Exercício 06.19

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.

 

Autômato Finito com Movimentos Vazios (AFε)

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

Autômato Finito Determinístico (AFD)

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

Autômato Finito Determinístico (AFD) Simplificado

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

Ybadoo   •   Copyright 2009/2025   •   GFDL