Logo Passei Direto
Buscar
8. Considerando que:
• toda linguagem livre de contexto também é senśıvel ao contexto;
• nem toda gramática livre de contexto é senśıvel ao contexto;
• há quatro tipos de gramáticas/linguagens segundo Chomsky,
as gramáticas abaixo são livres de contexto? São senśıveis ao contexto? Por que?
(a) G = (Σ, V, S, P ), onde Σ = {a, b}, V = {A,B}, S = A, P = {A → Ba, B → BB, Aa→ Bb, B → b, B → bA, A→ a, Ab→ λ}
(b) G = (Σ, V, S, P ), onde Σ = {0, 1}, V = {S}, P = {S → 0S1, S → λ}
Que linguagem é gerada pela gramática do item b?

User badge image
Questões para o Sucesso

ano passado

Respostas

User badge image

Ed Verified user icon

ano passado

Para responder a essa pergunta, é necessário analisar as características das gramáticas livres de contexto e sensíveis ao contexto. Uma linguagem livre de contexto é aquela em que as regras de produção são do tipo A → α, onde A é um símbolo não-terminal e α é uma sequência de símbolos terminais e/ou não-terminais. Já uma linguagem sensível ao contexto é aquela em que as regras de produção são do tipo αAβ → αγβ, onde α, β, e γ são sequências de símbolos terminais e/ou não-terminais, e A é um símbolo não-terminal. Analisando as gramáticas fornecidas: (a) G = (Σ, V, S, P ), onde Σ = {a, b}, V = {A,B}, S = A, P = {A → Ba, B → BB, Aa→ Bb, B → b, B → bA, A→ a, Ab→ λ} Essa gramática é livre de contexto, pois todas as regras de produção seguem o formato A → α. No entanto, ela não é sensível ao contexto, pois não possui regras do tipo αAβ → αγβ. (b) G = (Σ, V, S, P ), onde Σ = {0, 1}, V = {S}, P = {S → 0S1, S → λ} Essa gramática também é livre de contexto, pois todas as regras de produção seguem o formato A → α. Além disso, ela é sensível ao contexto, pois possui regras do tipo αAβ → αγβ. Portanto, a gramática do item (a) é livre de contexto, mas não sensível ao contexto. Já a gramática do item (b) é livre de contexto e sensível ao contexto.

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:

Mais perguntas desse material

Mais conteúdos dessa disciplina