Turmas - 2º Semestre de 2015
Turmas
2º Semestre de 2015

Apresente a árvore de derivação (parse tree) da expressão aritmética x = a + b * c - d * a + b, sobre a gramática livre de contexto apresentada a seguir.

G = ({A, B, C, D, E, F, G}, {a, b, c, d, x, =, +, -, *, /, (, )}, P, A)
P = {A → G=B
     B → DC | D
     C → +DC | -DC | +D | -D
     D → FE | F
     E → *FE | /FE | *F | /F
     F → (B) | G
     V → a | b | c | d | x}

Desenvolva uma Gramática Livre do Contexto (GLC) sobre o alfabeto Σ = {a, b, c, d}, que reconheça a linguagem L = {w | w possui ab ou bcda ou bca como prefixo, dab ou acab ou cad como subpalavra e dad ou aba ou bbc como sufixo}.

Qual é a linguagem da gramática livre do contexto contendo as seguintes regras de produção:

G = ({S, A, B}, {a, b}, P, S)
P = {S → AB
     A → Aa | a
     B → bB | ε}

1. {aⁿbⁿ | n ≥ 0}
2. {aⁿbⁿ | n > 0}
3. {aⁿb^m | n ≥ 0 e m ≥ 0}
4. {aⁿb^m | n ≥ 0 e m > 0}
5. {aⁿb^m | n > 0 e m ≥ 0}

O primeiro passo realizado pelo algoritmo de Exclusão de Símbolos Inúteis é a identificação das variáveis que constituem terminais presentes na gramática. Considerando a gramática livre de contexto a seguir, qual é o conjunto das variáveis que constituem terminais:

G = ({S, K, Q, R, T, U, W}, {a, b, c, d, , e}, P, S)
P = {S → aKbQ | cdW | eUd 
     K → Qc | Ubc
     Q → dU | cKdc
     R → abUTd | Uabc | acTe
     T → Tac | cTa | acd
     U → aQb | Kcd
     W → RRc | SbTU}

1. {S}
2. {S, T}
3. {S, R, T}
4. {S, R, T, W}
5. {S, R, T, U, W}

Converta para a Forma Normal de Chomsky a gramática livre de contexto apresentada a seguir.

G = ({S, A, B, C}, {a, b, c}, P, S)
P = {S → ABC | CBA
     a → a
     B → BaC | ACc
     C → aB | b}

Converta para a Forma Normal de Greibach a gramática livre de contexto apresentada a seguir.

G = ({S, A, B, C}, {a, b, c}, P, S)
P = {S → ABc
     A → BA | CcB | a
     B → ABb | b
     C → CA | c}

Observe a gramática a seguir.

G = ({S, A}, {a, b, c}, P, S)
P = {S → aS | bA
     A → cAa | ε}

Sobre essa gramática, assinale a alternativa correta:

1. É regular à direita e aceita a linguagem {aⁿbc^m | n ≥ 0 e m ≥ 0}.
2. É regular à esquerda e aceita a linguagem {aⁿbc^m | n > 0 e m ≥ 0}.
3. É livre de contexto e aceita a linguagem {aⁿbc^m | n > 0 e m ≥ 0}.
4. É regular à direita e aceita a linguagem {aⁿbc^m | n > 0 e m ≥ 0}.
5. É regular à esquerda e aceita a linguagem {aⁿbc^m | n ≥ 0 e m ≥ 0}.