Turmas - 2º Semestre de 2026
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}, δ, A, {B, D, E})

1. Os estados B e D são equivalentes.
2. Os estados B e E 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.

P₁ = {C₀, C₁}, com C₀ = {B, D, E} e C₁ = {A, C}

P₂ = {C₀, C₁, C₂}, com C₀ = {E}, C₁ = {B, D} e C₂ = {A, C}

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 P₂.

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

Correto, pois os estados B e D se encontram no mesmo conjunto C₁.

II. Os estados B e E são equivalentes.

Incorreto, pois o estado B se encontra no conjunto C₁, enquanto o estado E se encontra no conjunto C₀.

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

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

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

Incorreto, pois o estado D se encontra no conjunto C₁, enquanto o estado E se encontra no conjunto C₀.

Conforme exposto, a análise permite concluir que:

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