Aula 9 Gramáticas livres do contexto

Prévia do material em texto

Aula 9 – Gramáticas livres do contexto 
1. O formalismo gramática livre de contexto foi desenvolvido e sistematizado 
inicialmente por Avram Noam Chomsky, sendo esse mecanismo um exímio gerador das 
linguagens livres de contexto ou linguagem do tipo 2, conforme a hierarquia de Chomsky. 
Dessa forma, considere a gramática G1 = ({L, K}, {0, 1}, R, K), em que R tem as seguintes 
regras: 
K → 1K11 | L 
L → 0 L | ε 
Assinale a alternativa que traduz a gramática G1 em uma linguagem livre de contexto L1. 
 
A. A linguagem tem a seguinte estrutura: L1 = {12n0m1n | n > 0, m ≥ 0}. 
B. A linguagem tem a seguinte estrutura: L1 = {1n02m1n | n ≥ 0, m ≥ 0}. 
C. A linguagem tem a seguinte estrutura: L1 = {1n0m12n | n > 0, m ≥ 0}. 
D. A linguagem tem a seguinte estrutura: L1 = {1n0m12n | n ≥ 0, m ≥ 0}. 
E. A linguagem tem a seguinte estrutura: L1 = {1n0m1n | n ≥ 0, m ≥ 0}. 
 
2. As gramáticas livres de contexto foram desenvolvidas a partir de uma estratégia que 
utiliza substituições recursivas dentro de seus símbolos denominados variáveis ou não 
terminais. Em um símbolo não terminal, pode-se atribuir outro símbolo não terminal ou 
um terminal. 
Dessa forma, considere a linguagem L2 = { 0n1m2m33n | n ≥ 0, m > 0} e determine as regras 
usadas por essa gramática, em que será possível ver a utilização das chamadas recursivas 
dentro das variáveis. 
A. A gramática tem as seguintes regras: K → 0K33 | L, L → 1L22 | 12. 
B. A gramática tem as seguintes regras: K → 0K3333 | L, L → 1L22 | 12. 
C. A gramática tem as seguintes regras: K → 0K333 | L, L → 1L22 | 21. 
D. A gramática tem as seguintes regras: K → 0K333 | L, L → 1L22 | 11. 
E. A gramática tem as seguintes regras: K → 0K333 | L, L → 1L22 | 12. 
 
3. A formalização de uma ideia fornece argumentos sólidos ao se questionar sobre 
determinado escopo de atuação dela, tendo, assim, a seu favor, a precisão e 
notações/terminologias para se expressar melhor no tocante ao assunto. Aproveitando 
a ideia de formalização, as gramáticas livres de contextos também têm a sua. 
Dada a linguagem: 
L3 = { 1an#bn1 | n > 0} 
Determine a valoração de sua formalização. 
 
A. A 4-upla é: ({A, B}, {1, a, b}, {A → 1aAb, A → B, B → # }, Z). 
B. A 4-upla é: ({A, B}, {1, a, b, #}, {A → 1Ab1 , A → B, B → # }, A). 
C. A 4-upla é: ({A, B}, {1, a, b, #}, {A → 1aBb1 , B → aBb, B → # }, A). 
D. A 4-upla é: ({A, B}, {1, a, b, #}, {A → 1aAb1 , A → Bb, B → # }, A). 
E. A 4-upla é: ({A, B}, {1, a, b, c}, {A → 1aAb1 , A → B, B → # }, A). 
4. A árvore sintática é um recurso visual e uma abordagem para fazer a representação 
das gramáticas livres de contexto. Com ela, pode-se ver o funcionamento das 
substituições das variáveis por outras variáveis ou símbolos terminais utilizados na 
gramática em questão. 
Dadas as árvores sintáticas representadas nas figuras 1, 2, 3, 4 e 5, determine a gramática 
que a desenha. 
 
A. A gramática é: ({S}, {1, 0, ε }, {S → 0S0| 1S11| L, L → 0 | 1 | ε }, S). 
B. A gramática é: ({S, L}, {1, 0}, {S → 0S0| 1S1| L, L → 10 | 1 | ε }, S). 
C. A gramática é: ({S, L}, {1, 0}, {S → 0S0| 1S1| L, L → 0 | 1 | ε }, S). 
D. A gramática é: ({S}, {1, 0, ε }, {S → 0S0| 1S1| L, L → 0 | 1 | ε }, S). 
E. A gramática é: ({S, L}, {1, 0, ε, # }, {S → 0S1| 1S1| L, L → 0 | 1 | ε }, S). 
 
 
5. O problema da ambiguidade é algo indesejado em linguagens de programação, visto 
que as linguagens de programação precisam trabalhar sobre um dado exato, sem 
dualidade de significado, ou seja, sem ambiguidade. Por exemplo, na linguagem C, a 
cláusula de condição if-then-else é bem definida e sem ambiguidade. Caso contrário, 
haveria problema para o compilador entender a sintaxe da estrutura em questão. 
De acordo com o conceito de ambiguidade em gramáticas livres de contexto, analise as 
afirmações a seguir e assinale a alternativa que contém apenas as corretas: 
I. Diz-se que uma cadeia é ambígua se tem mais de uma derivação implementável pela 
gramática. 
II. Diz-se que uma cadeia é ambígua se tem mais de uma árvore sintática para a derivação 
de uma mesma cadeia. 
III. Diz-se que uma gramática é ambígua se tem mais de uma derivação para a mesma 
cadeia. 
IV. Diz-se que uma árvore sintática produz cadeia ambiguamente somente se 
faz derivações à esquerda. 
V. O fato de uma linguagem não conseguir deixar de ser ambígua indica que se trata 
de uma linguagem inerentemente mbígua. 
 
A. II e III 
B. II e IV. 
C. II e V. 
D. III e IV. 
E. III e V.