Ed
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.
Já tem uma conta?
Ao continuar, você aceita os Termos de Uso e Política de Privacidade
Mais perguntas desse material