Turmas - 2º Semestre de 2025
Turmas
2º Semestre de 2025

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

Questão 06

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 seguintes afirmativas sobre a aplicação do processo de minimização de estados ao autômato finito determinístico apresentado a seguir.

M = ({a, b}, {q₀, q₁, q₂, q₃, q₄, q₅, q₆, q₇}, δ, q₀, {q₆, q₇})

1. Os estados q₄ e q₅ são redundantes, e poderiam ser combinados em um único estado sem alterar a linguagem que é reconhecida.
2. Os estados q₁ e q₃ são redundantes, e poderiam ser combinados em um único estado sem alterar a linguagem que é reconhecida.
3. Os estados q₆ e q₇ são redundantes, e poderiam ser combinados em um único estado sem alterar a linguagem que é reconhecida.
4. Os estados q₂ e q₃ são redundantes, e poderiam ser combinados em um único estado sem alterar a linguagem que é reconhecida.

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 06

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₀ = {q₆, q₇} e C₁ = {q₀, q₁, q₂, q₃, q₄, q₅}

P₂ = {C₀, C₁, C₂}, com C₀ = {q₆, q₇}, C₁ = {q₀} e C₂ = {q₁, q₂, q₃, q₄, q₅}

P₃ = {C₀, C₁, C₂, C₃}, com C₀ = {q₆, q₇}, C₁ = {q₀}, C₂ = {q₄, q₅} e C₃ = {q₁, q₂, q₃}

P₄ = {C₀, C₁, C₂, C₃, C₄}, com C₀ = {q₆, q₇}, C₁ = {q₀}, C₂ = {q₄, q₅}, C₃ = {q₃} e C₄ = {q₁, q₂}

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 q₄ e q₅ são redundantes, e poderiam ser combinados em um único estado sem alterar a linguagem que é reconhecida.

Correto, pois os estados q₄ e q₅ se encontram no mesmo conjunto C₂.

II. Os estados q₁ e q₃ são redundantes, e poderiam ser combinados em um único estado sem alterar a linguagem que é reconhecida.

Incorreto, pois o estado q₁ se encontra no conjunto C₄, enquanto o estado q₃ se encontra no conjunto C₃.

III. Os estados q₆ e q₇ são redundantes, e poderiam ser combinados em um único estado sem alterar a linguagem que é reconhecida.

Correto, pois os estados q₆ e q₇ se encontram no mesmo conjunto C₀.

IV. Os estados q₂ e q₃ são redundantes, e poderiam ser combinados em um único estado sem alterar a linguagem que é reconhecida.

Incorreto, pois o estado q₂ se encontra no conjunto C₄, enquanto o estado q₃ se encontra no conjunto C₃.

Conforme exposto, a análise permite concluir que:

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