Ybadoo - Soluções em Software Livre
Turmas
2º Semestre de 2026

  1. Ybadoo
  2. Turmas
  3. 2º Semestre de 2026
  4. Linguagens Formais e Autômatos
  5. Primeira Avaliação
  6. Questão 02

Questão 02

Em geral, a aplicação do método da construção de subconjuntos produz autômatos com estados redundantes, ou seja, estados que poderiam ser combinados em um único estado sem alterar a linguagem que é reconhecida. Analise as afirmativas sobre os estados redundantes do autômato finito determinístico apresentado a seguir.

M = ({a, b, c}, {A, B, C, D, E, F}, δ, A, {D, E, F})

Grafo com a função de transição de M
Autômato Finito Determinístico
  1. Os estados B e C são equivalentes.
  2. Os estados D e F são equivalentes.
  3. Os estados A e C são equivalentes.
  4. Os estados D e E são equivalentes.

A análise permite concluir que:

a. Apenas as afirmativas I e II estão corretas.

b. Apenas as afirmativas I e III estão corretas.

c. Apenas as afirmativas II e III estão corretas.

d. Apenas as afirmativas II e IV estão corretas.

e. Apenas as afirmativas III e IV estão corretas.

Solução da Questão 02

Para se descobrir a solução da questão, é necessário realizar o processo de minimização de estados do autômato finito determinístico apresentado.

P1 = {C0, C1}, com C0 = {D, E, F} e C1 = {A, B, C}

C0 = {D, E, F}
C0DEF
a   
b   
cC0 C0
C1 = {A, B, C}
C1ABC
aC1C1C1
bC0 C0
cC0 C0

P2 = {C0, C1, C2}, com C0 = {E}, C1 = {D, F} e C2 = {A, B, C}

C0 = {E}
C0E
a 
b 
c 
C1 = {D, F}
C1DF
a  
b  
cC0C0
C2 = {A, B, C}
C2ABC
aC2C2C2
bC1 C1
cC1 C1

P3 = {C0, C1, C2, C3}, com C0 = {E}, C1 = {D, F}, C2 = {B} e C3 = {A, C}

C0 = {E}
C0E
a 
b 
c 
C1 = {D, F}
C1DF
a  
b  
cC0C0
C2 = {B}
C2B
aC3
b 
c 
C3 = {A, C}
C3AC
aC2C2
bC1C1
cC1C1

Com o processo de minimização de estados do autômato finito determinístico concluído, é possível analisar cada uma das afirmações, utilizando como base a partição P3.

I. Os estados B e C são equivalentes.

Incorreto, pois o estado B se encontra no conjunto C2, enquanto o estado C se encontra no conjunto C3.

II. Os estados D e F são equivalentes.

Correto, pois os estados D e F se encontram no mesmo conjunto C1.

III. Os estados A e C são equivalentes.

Correto, pois os estados A e C se encontram no mesmo conjunto C3.

IV. Os estados D e E são equivalentes.

Incorreto, pois o estado D se encontra no conjunto C1, enquanto o estado E se encontra no conjunto C0.

Conforme exposto, a análise permite concluir que:

c. Apenas as afirmativas II e III estão corretas.

Ybadoo   •   Copyright 2009/2026   •   GFDL