Qual o número mínimo de estados necessários em um autômato determinístico baseado em eventos para reconhecer…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Qual o número mínimo de estados necessários em um autômato determinístico baseado em eventos para reconhecer todas as sequências que contenham dois eventos consecutivos 'alarm' em qualquer posição?
- A) 2 estados.
- B) 4 estados.
- C) 3 estados.
- D) 5 estados.
- E) 1 estado.
✅ Resposta correta: alternativa C
Resolução passo a passo
- Resolvi a questão por conta própria. Um autômato determinístico precisa memorizar, a cada evento lido, apenas o que é necessário para decidir se a sequência já contém dois eventos alarm consecutivos. Passo 2: São necessários três estados. O q0 é o inicial e significa que o último evento não foi alarm (ou que nenhum evento foi lido). O q1 significa que o último evento lido foi alarm, mas ainda não houve dois alarm seguidos. O q2 é final e absorvente e significa que o padrão já apareceu. Passo 3: A partir de q0, ler alarm leva a q1 e ler outro evento permanece em q0. A partir de q1, ler alarm leva a q2 e ler outro evento volta a q0. A partir de q2, qualquer evento permanece em q2. Passo 4: Esses três estados são suficientes e necessários, pois q0 e q1 se distinguem: a sequência alarm seguido de alarm é aceita a partir de q1 e não a partir de q0. Logo, o mínimo é 3, alternativa C, que coincide com o gabarito oficial. Passo 5: Por que as outras estão erradas: a alternativa A (2 estados) não basta, pois falta um estado final separado para o padrão já reconhecido; a alternativa B (4 estados) acrescenta um estado morto desnecessário, já que o autômato mínimo não precisa de estado de rejeição; a alternativa D (5 estados) superestima a memória, pois não é preciso um estado por posição; a alternativa E (1 estado) não consegue memorizar se o último evento foi alarm.
💡 Dica: Considere as transições necessárias para reconhecer os eventos.
Alternativa por alternativa
Acredita que basta distinguir se o último evento foi alarm, sem perceber que é preciso um estado final separado e absorvente para sinalizar que o padrão já ocorreu.
Acrescenta um estado morto de rejeição, achando que todo autômato precisa de um estado armadilha, o que não é necessário neste caso.
Por que engana: O aluno pode confundir o número de estados necessários para reconhecer sequências com o número de eventos a serem reconhecidos, subestimando a complexidade do padrão.
É preciso um estado inicial (nenhum 'alarm' recente), um estado que indica que o último evento foi 'alarm', e um estado de aceitação após dois 'alarm' consecutivos; três estados distinguem esses casos.
Cria um estado para cada posição ou contagem de eventos, superestimando a memória necessária sem reduzir o autômato ao mínimo.
Imagina que uma única máquina lê os eventos e aceita sem guardar memória do passado, confundindo reconhecimento de padrão com leitura sem registro de histórico.
Raio-X da questão
autômato determinístico
avaliacao
autômatos finitos · reconhecimento de padrões
Revisar conceitos de autômatos e reconhecimento de padrões.
O aluno pode confundir o número de estados necessários para reconhecer sequências com o número de eventos a serem reconhecidos, subestimando a complexidade do padrão.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Quais elementos são essenciais para construir um programa baseado em eventos utilizando autômatos?
- Em um autômato finito que processa eventos como símbolos, o que diferencia um autômato determinístico de um não…
- Escreva pseudocódigo de um autômato baseado em eventos que conte ocorrências do evento 'botao' e emita 'alarme' quando o…
- Um autômato é usado para controlar a luz de um semáforo. Quais estados esse autômato deve ter?
- Escreva o conjunto mínimo de transições, em formato 'origem --evento--> destino', para um autômato com estados…
- 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