Ao projetar um autômato finito que reconhece uma linguagem simples de comandos, qual procedimento reduz o…

Questão

Ao projetar um autômato finito que reconhece uma linguagem simples de comandos, qual procedimento reduz o número de estados sem alterar a linguagem aceita?

1. A) Aplicar um algoritmo de minimização de autômatos (por exemplo, Hopcroft) para agrupar estados equivalentes.
2. B) Utilizar uma abordagem de geração de estados aleatórios.
3. C) Adicionar mais estados para cada comando na linguagem.
4. D) Aumentar os limites de entradas para o autômato.
5. E) Remover qualquer estado que reconhece um comando válido.

✅ Resposta correta: alternativa A

Resolução passo a passo

1. O enunciado pergunta qual procedimento reduz o número de estados de um autômato finito sem alterar a linguagem que ele aceita.
2. Resolvendo por conta própria, a resposta é a minimização do autômato: estados que são equivalentes (têm o mesmo comportamento para toda cadeia de entrada, isto é, levam a aceitação ou rejeição de forma idêntica) podem ser agrupados em um único estado. Algoritmos como o de Hopcroft, ou o método de particionamento por equivalência, fazem exatamente isso e preservam a linguagem reconhecida.
3. Por isso a alternativa A está correta, coincidindo com o gabarito oficial.
4. A alternativa B está errada, pois gerar estados aleatoriamente não tem relação com preservar a linguagem e não garante redução.
5. A alternativa C está errada, pois adicionar estados aumenta o tamanho do autômato, o oposto do que se deseja.
6. A alternativa D está errada, pois aumentar limites de entrada não altera a quantidade de estados nem reduz nada na estrutura do autômato.
7. A alternativa E está errada, pois remover um estado que reconhece um comando válido muda a linguagem aceita, violando a condição do enunciado.

💡 Dica: Considere as propriedades dos autômatos finitos.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• — Se dois voluntários entregarem o mesmo aparelho, como saberemos onde ele está? — perguntou uma visitante ao chegar à…
• Monitores de um centro esportivo estão testando um placar digital para partidas de futsal, vôlei e basquete. Antes de…
• Por que duas pessoas que leem uma história na tela podem chegar a trechos diferentes? Para uma mostra comunitária…
• Caminhões recolhem livros em uma campanha fictícia para renovar bibliotecas de bairro. Em cada ponto de coleta…
• — Se chegarem novos tipos de objetos, vou precisar copiar tudo outra vez? — perguntou Joana, que ajuda no ponto de…
• — Se enviarmos as caixas sem organização, um abrigo poderá receber itens que não pediu e outro ficará sem produtos…

Todas as questões de Estratégias de solução de problemas - Decomposição