Matemática2ª sérieBNCC EM13MAT405Difícil⏱ longo

Projete um autômato baseado em eventos que reconheça o padrão 'ABBA' em sequências sobre o alfabeto {A,B}…

Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva

Habilidade BNCC EM13MAT405

Utilizar conceitos iniciais de uma linguagem de programação na implementação de algoritmos escritos em linguagem corrente e/ou matemática.

Fonte: Base Nacional Comum Curricular (MEC).

Questão

Projete um autômato baseado em eventos que reconheça o padrão 'ABBA' em sequências sobre o alfabeto {A,B}. Descreva estados, transições e condição de aceitação, considerando sobreposição de ocorrências.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Use 5 estados S0..S4 onde Si indica comprimento do prefixo de 'ABBA' reconhecido (S0 inicial, S4 aceitação). Transições: S0: A?S1, B?S0. S1 (A): A?S1, B?S2. S2 (AB): A?S1 (porque 'A' pode iniciar novo padrão), B?S3. S3 (ABB): A?S4 (padrão completo), B?S0. S4 (ABBA aceito): para permitir sobreposição, trate como se estivesse no estado correspondente ao maior sufixo de 'ABBA' que é prefixo: em A?S1, em B?S2. Aceitação: qualquer chegada a S4 indica ocorrência de 'ABBA'. Explique que esse autômato implementa as transições seguindo o princípio do prefixo-sufixo (como no algoritmo de busca de padrões), garantindo consumo linear da sequência e detecção de padrões sobrepostos.

Explicação

O autômato proposto utiliza estados que correspondem a cada etapa do reconhecimento do padrão 'ABBA', permitindo que o sistema retorne a estados anteriores para detectar sobreposições. As transições entre os estados são definidas de forma a garantir que, ao encontrar um caractere que pode iniciar um novo padrão, o autômato continue a funcionar de maneira eficiente. A condição de aceitação em S4 assegura que cada vez que o padrão completo é reconhecido, a sequência é validada, mantendo um consumo linear de tempo.

Raio-X da questão

Dificuldade Difícil

Bloom Criar

Leitura alto

Discriminação alto

Peso pedagógico alto

Autonomia do enunciado completo

Cobertura da habilidade multipla

🧪 Simulado🩺 Diagnóstico🧮 Exige cálculo🏠 Cotidiano🔗 Interdisciplinar⭐ Representativa✍️ interpretativa🧩 desafio

🎯 Conceito central

autômatos finitos

📌 Objetivo

avaliacao

🧱 Pré-requisitos

autômatos finitos · teoria de linguagens formais

📚 Reveja

Revisar conceitos de autômatos e reconhecimento de padrões.

⚠️ Erro mais comum

O aluno pode confundir a sequência correta de estados e transições, resultando em um autômato que não reconhece o padrão 'ABBA' corretamente.

🌎 Tema transversal

ciencia_tecnologia

🤝 Socioemocional

criatividade

🏫 Contexto

abstrato

Questões parecidas com resolução

Todas as questões de Leitura e interpretação de tabelas e gráficos (de colunas ou barras simples ou múltiplas) referentes a variáveis categóricas e variáveis numéricas

🔎 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