[TCOMP] Aula 9.7 - Gramáticas Sensíveis ao Contexto

e agora a gente vai falar das linguagens sensíveis ao contexto que são na verdade as linguagens do tipo um na hierarquia de chomsky então começando pela gramática uma gramática G ela é do tipo 1 ou sensível ao contexto se toda a produção respeita acidente restrição uma produção sensível ao contexto vai ser uma produção onde aí do lado esquerdo a gente tem uma cadeia ver de símbolos tanto do alfabeto Sigma quantas das variáveis essa cadeira pode ser sozinho seguido de um símbolo a e esse símbolo aí ele precisa ser um símbolo das variáveis depois de uma

palavra né de uma cadeia w que também é uma combinação de cílios antes do alfabeto Zig na ponte do alfabeto das variáveis o w também pode ser vazio esse lado esquerdo ele vai produzir uma palavra compostas que pelo mesmo ver pelo mesmo w e o que muda vai ser e nós temos que esse dizer ele também é uma palavra composta pelos símbolos de cima e dever mas agora não pode ser a palavra vazia e se não o ar ele estaria sendo reduzido com a palavra vazia a ideia de sensível ao contexto Band que a gente

só vai substituir o símbolo a na nossa produção quando ele estiver no contexto que tem a esquerda e ver e à direita um w a Então essa que a ideia do nome gramática sensível ao contexto é só vai substituir com ele tirar em volta de um contexto específico significa eu vou poder ter outra produção do tipo x a&w vai gerar uma outra coisa aqui porque eu contexto é diferente aquele está entre x e entre w a Então acha que a ideia do nome da gramática sensível ao contexto temos aqui uma exceção a palavra vazia que

a gente vai permitir e a nossa gramática Gere a palavra vazia apenas com a produção é se produz a palavra base a esse é o símbolo inicial da gramática contanto que é se não apareça do lado direito das Produções da gramática então você não pode ter essa aparecendo igual direito a gente tinha essa restrição lá nas linguagens livres de contexto Essas são as gramáticas sensíveis ao contexto e a gente tem que como o z ele nunca vai ser a palavra vazia quando a gente tem as formas sentenciais que são as palavras que vão ser gerados

a partir DS Até chegar na palavra final todas essas palavras intermediárias que contém símbolos de variáveis elas são chamadas de armas especiais essas formas sentenciais elas nunca diminui o comprimento tá então você vai gerando ao lava só aumenta o mantém o tamanho da palavra por causa dessa restrição que a gente tem aqui nas gramáticas sensíveis ao contexto muito bem se gera uma gramática sensível ao contexto a linguagem G e vai ser também é uma linguagem sensível aconteceu ou linguagem do tipo 1 e aqui a definição que a gente já tá acostumado a linguagem gerada por

G ao conjunto das palavras w pertencente ao Alberto de palavras taught existe para derivação com mais de uma produção de arte no do símbolo inicial da gramática e que gera w temos aqui uma outra gramática agora essa gramática que ela é sensível ao contexto e ela gera a linguagem a Mb Mc N para n maior igual um a dramática que a gente tinha visto no slide anterior ela gerada também essa linguagem para ele maior igual a zero se você voltar naquele site você vai ver que a gramática diferente ela é tão pouco mais simples aquela

não respeita as inscrições que a gente tem aqui para ser uma gramática sensível ao contexto City voltar aqui rapidinho aqui ó ela não respeita as restrições porque o s produz a palavra vazia ele aparece do lado direito da bom então não pode tá então essa aqui não é uma gramática sensível ao contexto muito bem então voltando aqui a nossa exemplo de gramática sensível ao contexto se você analisar que todos os Produções elas respeitam a regra de ser uma gramática acessível aconteça logo a linguagem gerada ela vai ser sensível ao contexto eu não vou mostrar aqui

mas a gente consegue fazer todas as suas derivações fazendo as substituições igual a gente fez no exemplo anterior a gente tem que ir na aula anterior a gente viu que essa linguagem a nbnn não é nível de contexto porque por causa do lema do bombeamento então outra ferramenta que a gente aprendeu ao longo do curso é mostrar que uma linguagem não é de um título precisa provar com o lema do bombeamento específico da crítica ou quer provar que a linguagem é daquele tipo mas você constrói um autômato que processa as linguagens aquele mesmo e se

a linguagem Hélio Ela é gerada por uma gramática sensível ao contexto a gente vai falar que ela é do tipo 1 e com isso a gente chega finalmente aqui nós grave nós linguagens do tipo um são as linguagens sensíveis ao contexto onde as gramáticas que as geram tem aquelas restrições à produção e aqui a gente tem uma linguagem livre de contexto aqui ela também é sensível mas o contrário não vale porque a gente acabou de falar e a gente tem que as linguagens sensíveis ao contexto elas são turnê reconhecíveis quem que eram Astúrias reconhecidos Era

exatamente as linguagens do tipo zero ou recursivamente enumeráveis e também elas são turen decidíveis a gente não vai provar isso mas elas são touring decididas por isso a gente pode falar e as linguagens touring decidíveis que aquelas recursivas elas são subgrupo que está entre o tipo zero e o tipo 1