Turmas - 1º Semestre de 2016
Turmas
1º Semestre de 2016

Em algumas aplicações, como compiladores e processadores de textos, frequentemente é conveniente representar a derivação de palavras na forma de árvore, partindo do símbolo inicial como a raiz, e terminando em folhas de terminais. Apresente a árvore de derivação da entrada e(a;a;a;a) sobre a gramática livre do contexto apresentada a seguir.

G = ({S, A, B, C, X, Y}, {a, e, (, ), ;}, P, S)
P = {S → A)
     A → CB
     B → ;XB | ε
     C → Y(X
     X → a
     Y → e}

Eventualmente, uma mesma palavra pode ser associada a duas ou mais árvores de derivação, determinando uma ambiguidade. Em muitas aplicações como, por exemplo, no desenvolvimento e otimização de alguns tipos de algoritmos de reconhecimento, é conveniente que a gramática usada não seja ambígua. Prove que a seguinte gramática livre do contexto é ambígua:

G = ({S}, {a, b}, {S → SS | a | b}, S)

Desenvolva uma gramática livre do contexto equivalente (que gere a mesma linguagem) a gramática livre do contexto apresentada na questão 02, mas que não seja ambígua.

G = ({S}, {a, b}, {S → Sa | Sb | a | b}, S)

A exclusão de produções vazias (da forma S → ε) pode determinar diversas modificações nas produções de uma gramática livre do contexto, visando a total eliminação desse tipo de produção. Por exemplo, a variável D, da gramática livre do contexto apresentada a seguir, possui originalmente 3 (três) produções, mas ao final da execução do algoritmo de exclusão de produções vazias, a variável D terá 4 (quatro) produções. Quantas produções a variável F terá após a execução do algoritmo de exclusão de produções vazias?

G = ({A, B, C, D, E, F, G, H}, {x, y, z}, P, A)
P = {A → F | zBC
     B → Gx | yADz
     C → AD | yz | BH
     D → Cxy | ε | Az
     E → CDA | y
     F → D | AxCDyA
     G → EA | xyE
     H → AyC | DCz}

1. 14
2. 15
3. 16
4. 17
5. 18

A exclusão de símbolos inúteis (não usados na geração de palavras de terminais) é realizada excluindo as produções que fazem referência a estes símbolos, bem como os próprios símbolos inúteis. Considerando a gramática livre do contexto apresentada a seguir, qual será o conjunto de variáveis após a execução do algoritmo de exclusão de símbolos inúteis?

G = ({S, R, X, Z, W, Y, K, T, A}, {a, b, c}, P, S)
P = {S → Wb | bT
     R → XbbA | YaZb
     X → Kc | aWb
     Z → c | Ab | cWb
     W → abX | KAc
     Y → AZc | KaX
     K → XR | WA
     T → S | Ta | KX | a}

1. {S, T}
2. {S, Y}
3. {S, Y, T}
4. {S, Z}
5. {S, Z, T}

Uma produção da forma A → B não adiciona informação alguma em termos de geração de palavras, a não ser que a variável A possa ser substituída por B. Neste caso, se B → α, então a produção A → B pode ser substituída por A → α. Por exemplo, a variável F, da gramática livre do contexto apresentada a seguir, possui originalmente 2 (duas) produções, mas ao final da execução do algoritmo de exclusão de produções da forma A → B, a variável F terá 3 (três) produções. Quantas produções a variável A terá após a execução do algoritmo de exclusão de produções da forma A → B?

G = ({A, B, C, D, E, F}, {x, y, z}, P, A)
P = {A → xBy | C
     B → zCx | CD
     C → E | xA | F
     D → EF | Axy
     E → xyz | B
     F → D | xBC}

1. 4
2. 5
3. 6
4. 7
5. 8

As formas normais estabelecem restrições rígidas na definição das produções, sem reduzir o poder de geração das gramáticas livre do contexto, sendo usadas principalmente no desenvolvimento de algoritmos (com destaque para reconhecedores de linguagens) e na prova de teoremas. Converta a gramática livre do contexto apresentada a seguir para a Forma Normal de Greibach.

G = ({S, W, A}, {x, y, z}, P, S)
P = {S → WA | z
     W → WAy | y
     A → SxW}

G = ({A, B, B₀, C, X₀, X₁, X₂, X₃, X₄, X₅, X₆, X₇, X₈, Y₀, Y₁, Y₂, Y₃, Y₄, Y₅}, {x, y, z}, P, A)
P = {A  → yB₀C | yC | z
     B  → yB₀ | y
     B₀ → yB₀CX₀BY₀B₀ | yCX₁BY₁B₀ | zX₂BY₂B₀ | yB₀CX₃BY₃ | yCX₄BY₄ | zX₅BY₅
     C  → yB₀CX₆B | yCX₇B | zX₈B
     X₀  → x
     X₁  → x
     X₂  → x
     X₃  → x
     X₄  → x
     X₅  → x
     X₆  → x
     X₇  → x
     X₈  → x
     Y₀  → y
     Y₁  → y
     Y₂  → y
     Y₃  → y
     Y₄  → y
     Y₅  → y}

Analise a gramática apresentada a seguir.

G = ({S, A, B, C}, {a, b},P, S)
P = {S   → aAbab
     aAb → aabbA | ab
     bAb → bbA
     bAa → baB
     aBa → aaB
     aBb → Caabb
     aCa → Caa
     bC  → Cb
     aCb → aAb}

Sobre essa gramática, assinale a alternativa correta:

1. É livre de contexto e aceita a linguagem {aⁿbⁿaⁿbⁿ | n ≥ 1}.
2. É sensível ao contexto e aceita a linguagem {aⁿbⁿaⁿbⁿ | n ≥ 1}.
3. É sensível ao contexto e aceita a linguagem {aⁿb²ⁿaⁿ | n ≥ 1}.
4. É irrestrita e aceita a linguagem {aⁿbⁿaⁿbⁿ | n ≥ 1}.
5. É irrestrita e aceita a linguagem {aⁿb²ⁿaⁿ | n ≥ 1}.