Please enable JavaScript.
Coggle requires JavaScript to display documents.
Tipo 1 Sensíveis ao contexto (Diferenças (Livre de contexto (A ->…
Tipo 1
Sensíveis ao contexto
Exemplo
Uma gramático que não é livre de contexto
L= {0n 1n 0n | n>=0}
000001111100000
(Usando o pumping Lemma para gramática livre de contexto prova isso)
Diferenças
Livre de contexto
A -> theta
A esquerda
Elemento chave, que simboliza o não terminal
A direita
Pode ser terminal ou não terminal
Sensíveis ao contexto
AlphaABetha -> AlphaGamaBetha
A esquerda
Aqui é diferente, Aqui temos context em volta do não terminal A
Essa regra só será aplicada em situações especificas, em que o A e precendido por alpha e seguido por betha
Não mudamos o contexto, mas mudamos somente o A, substituindo por GAMA
A direita
Como a livre de contexto, aqui pode ser terminal ou não terminal
Exemplo a ser feito
L= {1n 2n 3n | n>=1}
Abordagem
Cada A se tornará em 1 Cada B se tornará em 2 Cada C se tornará em 3
S => .... AAABBBCCC => ... 1111222333
Começaremos com o simbolo inicial
Após a derivação teremos a forma da sentença, um grupo de A's seguidos por um grupo de B's e C's
A se tornará 1 B 2 e C 3
Inicio
111BBBCCC
A sentença irá iniciar com o 1
O A não vai será usado, pois precisamos de um contexto
Nessa ponto iremos converter B em 2 e C em 3
1B -> 12 2B -> 22 2C ->23 3C -> 33
111BBBCCC
1112BBCCC
11122BCCC
111222CCC
1112223CC
1 more item...
Regras para converter
Note: ... CB ... nunca pode ser reduzido. "C" só pode se tornar em "3" e "3B" não pode ser reduzido . B's deve vim antes dos C's
Passos de resolução
Passo 1:
Gerar o numero dorreto de 1's, B's, e C's. Mas não na ordem correta
S -> 1SBC S-> E
Para cada 1 temos B e C
Fazer arvore
Passo 2:
Colocar o "B's" na frente dos C's
CB->BC
Passo 3:
Transformar "B" em "2" e "C" em "3"
regras que vemos anteriormente
Obs: No passo 2 a regra não é sensível ao contexto, não podemos dizer quem é o contexto dessa regra. essa regra é de uma gramática do tipo 0 e não é permitido.
Passo 2 Solução: CB -> HB HB -> HC HC -> BC