Assinale a única alternativa que contém a disposição correta da esquerda para a direita, em ordem crescente, dos tipos de gramática que, segundo a hierarquia de Chomsky, geram as linguagens.
A - Gramáticas regulares → Gramáticas livres de contexto → Gramáticas sensíveis ao contexto → Gramáticas com estrutura de frase.
B - Gramáticas com estrutura de frase → Gramáticas sensíveis ao contexto → Gramáticas livres de contexto → Gramáticas regulares.
C - Gramáticas livres de contexto → Gramáticas com estrutura de frase → Gramáticas sensíveis ao contexto → Gramáticas regulares.
D - Gramáticas livres de contexto → Gramáticas regulares → Gramáticas com estrutura de frase → Gramáticas sensíveis ao contexto.
E - Gramáticas regulares → Gramáticas com estrutura de frase→ Gramáticas sensíveis ao contexto → Gramáticas livres de contexto.

Question

Assinale a única alternativa que contém a disposição correta da esquerda para a direita, em ordem crescente, dos tipos de gramática que, segundo a ...

Ed · Answer

Para responder a essa pergunta, precisamos entender a hierarquia de Chomsky, que classifica as gramáticas em quatro tipos, da mais simples para a mais complexa:

1. **Gramáticas Regulares**: São as mais simples e geram linguagens regulares.
2. **Gramáticas Livres de Contexto**: Um nível acima, geram linguagens livres de contexto.
3. **Gramáticas Sensíveis ao Contexto**: Um nível mais complexo, geram linguagens sensíveis ao contexto.
4. **Gramáticas com Estrutura de Frase**: Também conhecidas como gramáticas de tipo 0, são as mais gerais e podem gerar qualquer linguagem.

Com isso em mente, a ordem correta, da mais simples para a mais complexa, é:

**Gramáticas Regulares → Gramáticas Livres de Contexto → Gramáticas Sensíveis ao Contexto → Gramáticas com Estrutura de Frase.**

Analisando as alternativas:

A - Gramáticas regulares → Gramáticas livres de contexto → Gramáticas sensíveis ao contexto → Gramáticas com estrutura de frase. (CORRETA)

B - Gramáticas com estrutura de frase → Gramáticas sensíveis ao contexto → Gramáticas livres de contexto → Gramáticas regulares. (INCORRETA)

C - Gramáticas livres de contexto → Gramáticas com estrutura de frase → Gramáticas sensíveis ao contexto → Gramáticas regulares. (INCORRETA)

D - Gramáticas livres de contexto → Gramáticas regulares → Gramáticas com estrutura de frase → Gramáticas sensíveis ao contexto. (INCORRETA)

E - Gramáticas regulares → Gramáticas com estrutura de frase → Gramáticas sensíveis ao contexto → Gramáticas livres de contexto. (INCORRETA)

Portanto, a alternativa correta é a **A**.

Teoria da Computação

Conceitos básicos de autômatos e

Respostas

Ainda com dúvidas?

Essa pergunta também está no material:

Conceitos básicos de autômatos e

As operações algébricas sobre conjuntos usuais são definidas como: União, Interseção, Diferença.
Quais são as propriedades importantes das operações algébricas sobre conjuntos?

Um conjunto é considerado finito se contém um número finito de elementos; caso contrário, ele é infinito.
Como podemos definir um conjunto unitário?

Uma função é uma regra que atribui aos elementos de um conjunto um elemento único de outro conjunto.
Como podemos definir uma função injetora?

Os grafos serão muito úteis na construção de autômatos finitos (similares a máquinas de estado).
O que é um grafo e como ele é representado?

Uma árvore é um grafo: Simples, Acíclico (não possui ciclos), Conexo (existe caminho entre quaisquer dois de seus vértices).
Quais são as características que definem uma árvore?

Sabendo que o conjunto A = {0, 1, 3, 4, 5, 7} e A – B = {1, 3, 5, 7}, então o conjunto B é:
A
{0, 1, 4, 5}
{0, 1, 4, 5, 7}
{0, 4}
{0, 1, 5}
{}

Considere o conjunto A com 3 elementos; o B, com 4; e o C, com 5. Nesse caso, verificamos que:
A
tem, no máximo, 2 elementos.
tem, no máximo, 5 elementos.
tem, no máximo, 3 elementos.
tem, no máximo, 3 elementos.
tem 3 elementos, pelo menos.

Mais conteúdos dessa disciplina

Teoria da Computação

Conceitos básicos de autômatos e

Respostas

Ainda com dúvidas?

Essa pergunta também está no material:

Conceitos básicos de autômatos e

As operações algébricas sobre conjuntos usuais são definidas como: União, Interseção, Diferença.Quais são as propriedades importantes das operações algébricas sobre conjuntos?

Um conjunto é considerado finito se contém um número finito de elementos; caso contrário, ele é infinito.Como podemos definir um conjunto unitário?

Uma função é uma regra que atribui aos elementos de um conjunto um elemento único de outro conjunto.Como podemos definir uma função injetora?

Os grafos serão muito úteis na construção de autômatos finitos (similares a máquinas de estado).O que é um grafo e como ele é representado?

Uma árvore é um grafo: Simples, Acíclico (não possui ciclos), Conexo (existe caminho entre quaisquer dois de seus vértices).Quais são as características que definem uma árvore?

Sabendo que o conjunto A = {0, 1, 3, 4, 5, 7} e A – B = {1, 3, 5, 7}, então o conjunto B é:A{0, 1, 4, 5}{0, 1, 4, 5, 7}{0, 4}{0, 1, 5}{}

Considere o conjunto A com 3 elementos; o B, com 4; e o C, com 5. Nesse caso, verificamos que:Atem, no máximo, 2 elementos.tem, no máximo, 5 elementos.tem, no máximo, 3 elementos.tem, no máximo, 3 elementos.tem 3 elementos, pelo menos.

Mais conteúdos dessa disciplina

As operações algébricas sobre conjuntos usuais são definidas como: União, Interseção, Diferença.
Quais são as propriedades importantes das operações algébricas sobre conjuntos?

Um conjunto é considerado finito se contém um número finito de elementos; caso contrário, ele é infinito.
Como podemos definir um conjunto unitário?

Uma função é uma regra que atribui aos elementos de um conjunto um elemento único de outro conjunto.
Como podemos definir uma função injetora?

Os grafos serão muito úteis na construção de autômatos finitos (similares a máquinas de estado).
O que é um grafo e como ele é representado?

Uma árvore é um grafo: Simples, Acíclico (não possui ciclos), Conexo (existe caminho entre quaisquer dois de seus vértices).
Quais são as características que definem uma árvore?

Sabendo que o conjunto A = {0, 1, 3, 4, 5, 7} e A – B = {1, 3, 5, 7}, então o conjunto B é:
A
{0, 1, 4, 5}
{0, 1, 4, 5, 7}
{0, 4}
{0, 1, 5}
{}

Considere o conjunto A com 3 elementos; o B, com 4; e o C, com 5. Nesse caso, verificamos que:
A
tem, no máximo, 2 elementos.
tem, no máximo, 5 elementos.
tem, no máximo, 3 elementos.
tem, no máximo, 3 elementos.
tem 3 elementos, pelo menos.