Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — IF-MG 2024

Algoritmos e Estrutura de DadosAlgoritmos
Código
qg240206
Banca
IF-MG
Órgão
IF-MG
Ano
2024
Nível
Superior
Cargo
PROFESSOR EBTT - Sistemas da Computação - Bambuí
Os autômatos finitos são amplamente utilizados na computação devido à sua simplicidade e eficiência para resolver problemas que envolvem o reconhecimento de padrões e a manipulação de cadeias de caracteres. Sobre autômatos finitos, considere as seguintes afirmações:I - A máquina de estados de um autômato finito, também denominada controle finito, é definida pelo conjunto de estados e pela função de transição.II - Uma cadeia de entrada é aceita por um autômato quando, após esgotamento da cadeia, o estado corrente do autômato é do tipo final.III - Estados inacessíveis são aqueles para os quais não existe no autômato qualquer caminho, formado por transições válidas, que permita atingi-los a partir do estado inicial do autômato.IV - Uma das características dos autômatos finitos é a existência de memória auxiliar.Assinale a alternativa que apresenta apenas afirmações corretas:
  1. AII, III e IV, apenas.
  2. BI, III e IV, apenas.
  3. CI, II e IV, apenas.
  4. DI, II e III, apenas.
  5. EI, II, III e IV.
Revelar gabarito e comentário

GabaritoD — I, II e III, apenas.

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ômatos Finitos

Gabarito: letra D. Estão corretas apenas as afirmações I, II e III. A afirmação IV é falsa porque autômatos finitos não possuem memória auxiliar; eles são modelos de computação com capacidade de memória limitada ao estado atual. A presença de memória auxiliar (como uma pilha) é característica de autômatos mais poderosos, como autômatos de pilha ou máquinas de Turing.

Afirmação I — ✅ Correta

A máquina de estados de um autômato finito é composta pelo conjunto de estados e pela função de transição, que definem como o autômato se comporta. Essa é a definição padrão do controle finito.

Afirmação II — ✅ Correta

A aceitação de uma cadeia ocorre quando, após processar todos os símbolos, o autômato se encontra em um estado final (ou de aceitação). É a condição clássica de aceitação para autômatos finitos.

Afirmação III — ✅ Correta

Estados inacessíveis são aqueles que não podem ser alcançados a partir do estado inicial por meio de nenhuma sequência de transições válidas. Tais estados são irrelevantes para o comportamento do autômato e podem ser removidos durante a minimização.

Afirmação IV — ❌ Incorreta

Autômatos finitos não possuem memória auxiliar. Sua única forma de memória é o estado corrente. Modelos com memória auxiliar, como autômatos de pilha (que usam uma pilha) ou máquinas de Turing (que usam uma fita), são mais expressivos e conseguem reconhecer linguagens mais complexas.

Autômato finito
  • 1Possui
    • Conjunto de estados
    • Função de transição
    • Estados finais (aceitação)
    • Estados inacessíveis (removíveis)
  • 2Não possui
    • Memória auxiliar (pilha/fita)
LEVEL · soulevel.com.br

Gabarito: letra D — apenas as afirmativas I, II e III estão corretas.

Link permanente: /questoes/qg240206