Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — IFB 2017

Algoritmos e Estrutura de DadosAlgoritmos
Código
qq283585
Banca
IFB
Órgão
IFB
Ano
2017
Nível
Superior
Cargo
Professor - Informática
Considerando-se a definição sobre autômatos finitos e linguagens, assinale a única alternativa que contém a disposição correta (da esquerda para a direita) dos tipos de gramática segundo o critério da abrangência das linguagens geradas (gramática mencionada gera linguagem que abrange a linguagem gerada pela gramática a sua direita – hierarquia de Chomsky).
  1. AGramáticas irrestritas > Gramáticas livres de contexto > Gramáticas sensíveis ao contexto > Gramáticas regulares.
  2. BGramáticas regulares > Gramáticas livres de contexto > Gramáticas sensíveis ao contexto > Gramáticas irrestritas.
  3. CGramáticas livres de contexto > Gramáticas irrestritas > Gramáticas sensíveis ao contexto > Gramáticas regulares.
  4. DGramáticas irrestritas > Gramáticas sensíveis ao contexto > Gramáticas livres de contexto > Gramáticas regulares.
  5. EGramáticas regulares > Gramáticas sensíveis ao contexto > Gramáticas livres de contexto > Gramáticas irrestritas.
Revelar gabarito e comentário

GabaritoD — Gramáticas irrestritas > Gramáticas sensíveis ao contexto > Gramáticas livres de contexto > Gramáticas regulares.

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”.

Hierarquia de Chomsky

Gabarito: letra D. A Hierarquia de Chomsky classifica as gramáticas pela abrangência das linguagens geradas, da mais abrangente para a menos: Irrestritas > Sensíveis ao Contexto > Livres de Contexto > Regulares. A única alternativa que segue exatamente essa ordem é a D.

A questão cobra a memorização da ordem decrescente de poder gerativo. Confira cada alternativa:

Hierarquia de Chomsky
  • 1Tipo 0: Irrestritas (mais abrangente)
  • 2Tipo 1: Sensíveis ao contexto
  • 3Tipo 2: Livres de contexto
  • 4Tipo 3: Regulares (mais restrita)
LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

Inverte a posição das gramáticas sensíveis ao contexto e livres de contexto. A ordem correta coloca as sensíveis antes das livres.

Alternativa B — ❌ Incorreta

Apresenta a ordem inversa (da mais restrita para a mais abrangente), o que contraria o enunciado.

Alternativa C — ❌ Incorreta

Coloca as gramáticas livres de contexto antes das irrestritas, o que é incorreto: as irrestritas são as mais abrangentes.

Alternativa D — ✅ Correta ⟵ GABARITO

Exibe a sequência exata da Hierarquia de Chomsky: Irrestritas > Sensíveis ao Contexto > Livres de Contexto > Regulares.

Alternativa E — ❌ Incorreta

Ordem inversa (regulares primeiro) e também troca a posição de sensíveis e livres.

PEGA ESSA DICA!

Memorize a hierarquia associando os tipos aos números: Tipo 0 (Irrestritas) > Tipo 1 (Sensíveis ao Contexto) > Tipo 2 (Livres de Contexto) > Tipo 3 (Regulares). Uma dica é lembrar da sigla "ISLR" (Irrestritas, Sensíveis, Livres, Regulares) ou associar a capacidade: quanto maior o número, mais restrita a linguagem.

Gabarito: letra D

Link permanente: /questoes/qq283585