Ao projetar um autômato finito que reconhece uma linguagem simples de comandos, qual procedimento reduz o…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir soluções de problemas usando a técnica de decomposição e automatizar tais soluções usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).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?
- A) Aplicar um algoritmo de minimização de autômatos (por exemplo, Hopcroft) para agrupar estados equivalentes.
- B) Utilizar uma abordagem de geração de estados aleatórios.
- C) Adicionar mais estados para cada comando na linguagem.
- D) Aumentar os limites de entradas para o autômato.
- E) Remover qualquer estado que reconhece um comando válido.
✅ Resposta correta: alternativa A
Resolução passo a passo
- O enunciado pergunta qual procedimento reduz o número de estados de um autômato finito sem alterar a linguagem que ele aceita.
- 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.
- Por isso a alternativa A está correta, coincidindo com o gabarito oficial.
- A alternativa B está errada, pois gerar estados aleatoriamente não tem relação com preservar a linguagem e não garante redução.
- A alternativa C está errada, pois adicionar estados aumenta o tamanho do autômato, o oposto do que se deseja.
- 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.
- 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
Algoritmos de minimização identificam e fundem estados que têm comportamento indistinto para todas as entradas, preservando a linguagem reconhecida.
O aluno pode imaginar que um procedimento aleatório ou 'sorteado' de estados simplificaria o autômato, sem perceber que a redução precisa ser sistemática e baseada em equivalência de estados.
O aluno pode pensar que, por ser mais detalhado, um autômato com mais estados é mais preciso ou organizado, confundindo complexidade descritiva com eficiência.
Por que engana: Confundir a minimização de autômatos com a adição de estados, acreditando que mais estados melhoram a eficiência do autômato.
O aluno pode confundir os limites de entrada (tamanho ou alfabeto das cadeias) com a estrutura interna do autômato, achando que alterar esses limites mexe no número de estados.
O aluno pode acreditar que eliminar estados 'desnecessários' basta para simplificar, sem notar que remover um estado que aceita um comando válido altera a linguagem reconhecida.
Raio-X da questão
autômato finito
avaliacao
minimização de autômatos · estados equivalentes
Revisar os conceitos de minimização de autômatos finitos.
Confundir a minimização de autômatos com a adição de estados, acreditando que mais estados melhoram a eficiência do autômato.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Projete um autômato baseado em eventos que valide sequências de comandos de um robô educacional: o comando 'iniciar'…
- Quais elementos são essenciais para construir um programa baseado em eventos utilizando autômatos?
- Por que uma catraca às vezes apita e, em outras, libera a passagem sem demora? Em um terminal de ônibus, a empresa de…
- Descreva como você usaria um autômato simples para controlar o funcionamento de um semáforo. Inclua os estados e…
- Um autômato é usado para controlar a luz de um semáforo. Quais estados esse autômato deve ter?
- Qual o número mínimo de estados necessários em um autômato determinístico baseado em eventos para reconhecer todas as…
Todas as questões de Estratégias de solução de problemas - Decomposição
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog