Em um autômato finito que processa eventos como símbolos, o que diferencia um autômato determinístico de um…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar os limites da Computação para diferenciar o que pode ou não ser automatizado, buscando uma compreensão mais ampla dos limites dos processos mentais envolvidos na resolução de problemas.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em um autômato finito que processa eventos como símbolos, o que diferencia um autômato determinístico de um não determinístico?
- A) Em autômatos determinísticos, há múltiplas transições possíveis por par (estado, símbolo).
- B) Um autômato não determinístico tem transições indefinidas por cada par (estado, símbolo).
- C) Autômatos não determinísticos têm comportamentos previsíveis, assim como os determinísticos.
- D) Autômatos não determinísticos não podem ser convertidos em determinísticos.
- E) No determinístico há no máximo uma transição por par (estado, símbolo); no não determinístico podem existir múltiplas transições.
✅ Resposta correta: alternativa E
Resolução passo a passo
- Recordar a definição formal de autômato finito determinístico (AFD). Em um AFD, a função de transição leva cada par (estado, símbolo) a exatamente um estado; portanto, há no máximo uma transição possível para cada par (estado, símbolo) e, a cada passo, o caminho da computação é único.
- Recordar o autômato finito não determinístico (AFN). Em um AFN, a função de transição pode levar um par (estado, símbolo) a zero, um ou vários estados simultaneamente. Assim, podem existir múltiplas transições para o mesmo par (estado, símbolo), e a computação pode seguir vários caminhos em paralelo, sendo aceita a palavra se algum caminho terminar em estado final.
- Comparar com as alternativas. A alternativa E descreve exatamente essa diferença: no determinístico, no máximo uma transição por par (estado, símbolo); no não determinístico, podem existir múltiplas transições. Esta é a resposta correta, e coincide com o gabarito oficial.
- Analisar as demais alternativas. A alternativa A está errada porque inverte os conceitos: a múltipla transição por par é característica do não determinístico, não do determinístico. A alternativa B está errada porque transições 'indefinidas' não são o que caracteriza o AFN; no AFN o par pode ter várias transições ou nenhuma, mas a definição não é de transições indefinidas. A alternativa C está errada porque o AFN não tem comportamento previsível no sentido de caminho único; sua computação é não determinística. A alternativa D está errada porque todo AFN pode ser convertido em um AFD equivalente pela construção de subconjuntos.
- Conclusão. A alternativa correta é a E, em concordância com o gabarito oficial.
💡 Dica: Defina as características de cada tipo de autômato.
Alternativa por alternativa
O aluno inverteu as definições, atribuindo ao determinístico a possibilidade de múltiplas transições por par (estado, símbolo), que é justamente a característica do não determinístico.
Por que engana: Confundir as definições de autômatos determinísticos e não determinísticos, acreditando que ambos têm múltiplas transições por par (estado, símbolo).
O aluno associa o não determinismo a transições 'indefinidas', confundindo a ausência de unicidade com falta de definição da função de transição, que no AFN está bem definida e pode levar a vários estados.
O aluno supõe que, por a palavra ser aceita ou rejeitada de forma única, o AFN também tem comportamento previsível e de caminho único, como o determinístico, ignorando a computação paralela.
O aluno acredita que o não determinismo impede qualquer equivalência com autômatos determinísticos, desconhecendo a construção por subconjuntos que converte qualquer AFN em um AFD equivalente.
Determinismo exige transição única para cada par (estado,símbolo), garantindo comportamento previsível e um próximo estado bem definido para cada entrada.
Raio-X da questão
autômatos determinísticos e não determinísticos
avaliacao
autômatos finitos · transições em autômatos
Revisar as definições de autômatos finitos e suas classificações.
Confundir as definições de autômatos determinísticos e não determinísticos, acreditando que ambos têm múltiplas transições por par (estado, símbolo).
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Em ciência da computação, como se diferencia um algoritmo determinístico de um não-determinístico quanto ao…
- Qual o número mínimo de estados necessários em um autômato determinístico baseado em eventos para reconhecer todas as…
- Quais elementos são essenciais para construir um programa baseado em eventos utilizando autômatos?
- Em um autômato orientado a eventos, o que provoca a transição imediata entre estados?
- Por que uma catraca às vezes apita e, em outras, libera a passagem sem demora? Em um terminal de ônibus, a empresa de…
- Em programação por eventos, qual é o papel de uma variável 'estado' em um autômato dirigido por eventos ao processar uma…
🔎 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