Questão de Algoritmos e Estrutura de Dados — Algoritmos — CESPE / CEBRASPE 2022
Algoritmos e Estrutura de Dados›Algoritmos
Código
ce141585
Banca
CESPE / CEBRASPE
Órgão
POLITEC-RO
Ano
2022
Nível
Superior
Cargo
POLITEC - RO - Perito Criminal - Área 6 (Ciências da Computação/Informática/Análise de Sistemas)
O autômato finito determinístico
Acorresponde à função de transição que recebe um estado ou um símbolo de entrada que sempre retorna um conjunto de estados como resultado.
Btem a capacidade de adivinhar algo sobre sua entrada ao testar valores.
Cpode, para cada entrada, transitar a partir do seu estado atual em um e somente um estado.
Dpermite zero, uma ou n transições para os estados de entrada.
Econsegue estar em vários estados ao mesmo tempo.
Revelar gabarito e comentário▾
GabaritoC — pode, para cada entrada, transitar a partir do seu estado atual em um e somente um estado.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Autômato Finito Determinístico (AFD)
Gabarito: letra C. O autômato finito determinístico (AFD ou DFA) é definido por uma função de transição que, para cada combinação de estado atual e símbolo de entrada, especifica exatamente um próximo estado. Essa unicidade é a essência do determinismo — diferentemente do autômato finito não determinístico (AFN), que pode admitir múltiplas transições, nenhuma transição ou transições que levam a um conjunto de estados.
A tabela abaixo resume as principais diferenças:
Característica
AFD (Determinístico)
AFN (Não Determinístico)
Transição para cada entrada
Exatamente um estado
Um conjunto de estados (vazio, um ou vários)
Comportamento
Único caminho de execução
Pode haver múltiplos caminhos
Estados simultâneos
Apenas um
Vários ao mesmo tempo
Poder de expressão
Equivalente ao AFN
Equivalente ao AFD
Autômato finito
1Determinístico (AFD)
Transição: exatamente um estado
Comportamento: único caminho
Estados simultâneos: apenas um
2Não determinístico (AFN)
Transição: conjunto de estados
Comportamento: múltiplos caminhos
Estados simultâneos: vários
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
Afirma que a função de transição retorna um conjunto de estados. Isso é característica do AFN (não determinístico). No AFD, a transição retorna um único estado.
Alternativa B — ❌ Incorreta
Menciona a capacidade de “adivinhar” sobre a entrada. Essa é uma propriedade intuitiva do não determinismo — o AFN pode “escolher” entre várias transições e, na prática, simula-se essa escolha por backtracking ou paralelismo. O AFD não adivinha; sua computação é estritamente determinística.
Alternativa C — ✅ Correta ⟵ GABARITO
“Pode, para cada entrada, transitar a partir do seu estado atual em um e somente um estado.” Essa é a definição clássica do AFD: para cada par (estado, símbolo) há uma transição única bem definida.
Alternativa D — ❌ Incorreta
“Permite zero, uma ou n transições para os estados de entrada.” Essa flexibilidade (inclusive zero transições) é própria do AFN. No AFD, a função de transição é total (ou parcial no máximo uma) — nunca zero ou múltiplas para o mesmo par.
Alternativa E — ❌ Incorreta
“Consegue estar em vários estados ao mesmo tempo.” A capacidade de estar simultaneamente em múltiplos estados é uma forma de descrever a execução de um AFN (que, na prática, pode explorar vários caminhos concorrentemente). O AFD, em contraste, ocupa exatamente um estado a cada instante.
Conclusão: a única alternativa que descreve corretamente o autômato finito determinístico é a letra C.