Logo Passei Direto
Buscar

Teoria da Computação

Outros
A Hierarquia de Chomsky é a classificação de gramáticas formais em quatro níveis.
Quais são os tipos de gramáticas na Hierarquia de Chomsky?
Gramática tipo 0, Gramática tipo 1, Gramática tipo 2, Gramática tipo 3.
Gramática livre de contexto, Gramática sensível ao contexto, Gramática regular.
Gramática irrestrita, Gramática regular, Gramática sensível ao contexto.
Gramática de estrutura de frase, Gramática livre de contexto, Gramática regular.
User badge image
Progresso com Exercícios

há 3 meses

User badge image
Progresso com Exercícios

há 3 meses

Linguagens livres de contexto
47 pág.

Linguagens livres de contexto

Respostas

User badge image

Ed Verified user icon

há 3 meses

A Hierarquia de Chomsky classifica as gramáticas formais em quatro tipos: 1. Gramática Tipo 0: Gramáticas irrestritas (ou gramáticas de tipo 0). 2. Gramática Tipo 1: Gramáticas sensíveis ao contexto. 3. Gramática Tipo 2: Gramáticas livres de contexto. 4. Gramática Tipo 3: Gramáticas regulares. Esses tipos de gramáticas correspondem a diferentes classes de linguagens formais, com a Gramática Tipo 0 sendo a mais geral e a Tipo 3 a mais restrita.

Essa resposta te ajudou?

0
Dislike0
left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar essa resposta. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

Linguagens livres de contexto
47 pág.

Linguagens livres de contexto

Mais perguntas desse material

Antes de tudo, é preciso conhecer as seguintes definições: Símbolo, Alfabeto e Cadeia.
O que é um símbolo em linguagens formais?
Uma entidade definida como um ponto em geometria.
Um conjunto finito de símbolos.
Uma sequência de símbolos de comprimento finito.
Uma regra para definir se uma frase é válida em qualquer idioma.

Uma cadeia é definida como uma sequência de símbolos de comprimento finito.
Como é denotado o comprimento de uma cadeia w?
|w|
λ
Σ
n

A forma normal de Backus Naur (BNF) é uma notação formal para descrever a sintaxe de uma linguagem.
Qual é a função do símbolo ::= na notação BNF?
Denota 'é definido como'.
Denota 'ou'.
Denota uma escolha.
Denota um terminal.

A seguinte expressão define uma gramática livre de contexto P = {A→β | A ϵ V Λ β ϵ (V U T)*}. Avalie as afirmativas a seguir:
Quais as afirmativas estão corretamente relacionadas com uma gramática livre de contexto?
I. O lado esquerdo da produção contém exatamente uma variável.
II. No lado direito é possível qualquer combinação de símbolos do conjunto {V U T}*.
III. É uma gramática tipo 3, sendo importante para definir linguagens de programação.
A - II e III
B - I e III
C - I e II
D - I, II e III
E - II

Considere o seguinte subconjunto da gramática da linguagem C, expresso em BNF: As regras para identificadores de variáveis em linguagem C são:
Assinale a alternativa que representa corretamente a produção descrita no texto:
1. Um identificador é uma sequência de letras, dígitos e sublinhados.
2. Um identificador deve começar com uma letra ou sublinhado.
3. Os identificadores permitem letras maiúsculas e minúsculas.
A - , e ϵ T
B - {a|b|...|z|A|B|...|Z} ϵ T*
C - → é uma regra de produção válida
D - {0|1|...|9} ϵ(V U T)*
E - ::= λ

Qual das seguintes alternativas é uma produção unitária (T = Terminal e NT = Não terminal)?
A (cadeia de NT)→(cadeia de NT)
B (NT único)→(cadeia de NT)
C (NT)→(NT único)
D (cadeia de NT)→(NT único)
E (T único)→(T único)

Considerando os símbolos não geradores, avalie as seguintes alternativas:
Qual opção inclui afirmativas corretas?
I. Não geram nenhuma sequência de terminais e não terminais.
II. Não geram nenhuma sequência de terminais.
III. Não geram nenhuma sequência de produções.
A I e II
B II e III
C III
D II
E I

Quais as afirmativas são verdadeiras (V) e falsas (F)?
( ) Não fechada para união
( ) Fechada para concatenação
( ) Não fechada para complementação
( ) Fechada para fecho de Kleene
( ) Fechada para diferença
A - V, V, V, V, V
B - F, V, V, F, V
C - F, V, V, V, V
D - F, V, F, V, V
E - V, V, V, F, F

Quais são as afirmativas verdadeiras?
I - O lema de bombeamento para linguagens regulares é baseado no fato de que todas as cadeias em uma linguagem regular devem apresentar um certo padrão repetitivo.
II - O lema de bombeamento para LLC é usado para provar que certos conjuntos não são livres de contexto.
III - O lema de bombeamento pode ser outro tipo de forma normal, além da BNF, onde o número de símbolos à direita de uma produção é estritamente limitado.
A - I e II.
B - I e III.
C - I, II e III.
D - Somente I.
E - Somente III.

Mais conteúdos dessa disciplina