Questão de Algoritmos e Estrutura de Dados — Algoritmos — IBADE 2025
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg510948
Banca
IBADE
Órgão
Prefeitura de Rolim de Moura - RO
Ano
2025
Nível
Superior
Cargo
Analista de Sistemas
No contexto da teoria da computação, qual é a característica fundamental que define uma linguagem regular?
APode ser processada por uma máquina de Turing com fita infinita.
BRequer uma gramática livre de contexto para sua descrição.
CPode ser reconhecida por um autômato finito determinístico.
DNecessita de memória auxiliar para cadeias complexas.
EÉ exclusiva para linguagens de programação orientada a objetos.
Revelar gabarito e comentário▾
GabaritoC — Pode ser reconhecida por um autômato finito determinístico.
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”.
Linguagens Regulares
Gabarito: letra C. A característica fundamental que define uma linguagem regular é a possibilidade de ser reconhecida por um autômato finito determinístico (AFD) (ou não determinístico). Essa é a base da hierarquia de Chomsky, que classifica as linguagens formais em quatro níveis: regulares, livres de contexto, sensíveis ao contexto e recursivamente enumeráveis.
Hierarquia de Chomsky: Tipo 3: Regulares (Reconhecida por AFD/AFN, Expressões regulares); Tipo 2: Livres de contexto (Gramática livre de contexto, Autômato com pilha); Tipo 1: Sensíveis ao contexto; Tipo 0: Recursivamente enumeráveis (Máquina de Turing)
Alternativa A — ❌ Incorreta
Afirma que linguagens regulares podem ser processadas por uma máquina de Turing com fita infinita. Na verdade, qualquer linguagem recursivamente enumerável pode ser processada por uma máquina de Turing. As linguagens regulares são um subconjunto próprio dessas, mas sua característica definidora é o reconhecimento por autômato finito, não por máquina de Turing.
Alternativa B — ❌ Incorreta
Afirma que requerem uma gramática livre de contexto. Gramáticas livres de contexto geram linguagens livres de contexto, que são mais expressivas que as regulares. Linguagens regulares podem ser descritas por gramáticas regulares (tipo 3), não por gramáticas livres de contexto (tipo 2).
Alternativa C — ✅ Correta ⟵ GABARITO
Exatamente: a definição clássica de linguagem regular é aquela que pode ser reconhecida por um autômato finito determinístico (ou não determinístico). Isso decorre do teorema de Kleene e da correspondência com expressões regulares.
Alternativa D — ❌ Incorreta
Afirma que necessita de memória auxiliar para cadeias complexas. Autômatos finitos possuem memória limitada (apenas o estado atual) e não necessitam de memória auxiliar externa. Linguagens que exigem memória auxiliar (como uma pilha) são as livres de contexto ou superiores.
Alternativa E — ❌ Incorreta
Afirma que é exclusiva para linguagens de programação orientada a objetos. O conceito de linguagem regular é totalmente independente de paradigmas de programação. Expressões regulares e autômatos finitos são usados em diversos contextos, não apenas em linguagens orientadas a objetos.