Turmas - 1º Semestre de 2015
Turmas
1º Semestre de 2015

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

G = ({A, E, T, F, V}, {a, b, c, d, e, f, x, =, +, -, *, /, (, )}, P, A)
P = {A → V=E
     E → T+E | T-E | T
     T → F*T | F/T | F
     F → (E) | V
     V → a | b | c | d | e | f | x}

Desenvolva uma Gramática Livre do Contexto (GLC) sobre o alfabeto Σ = {1, 2, 3, 4}, que reconheça a linguagem L = {w | w possui 1234 ou 1212 ou 3434 como prefixo, 3412 ou 4421 ou 1243 ou 2234 como subpalavra e 2212 ou 1123 ou 2431 ou 3444 como sufixo}.

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

S → ASb | c
A → a

1. {aⁿcb | n ∈ ℵ}
2. {acbⁿ | n ∈ ℵ}
3. {aⁿcⁿb | n ∈ ℵ}
4. {aⁿcbⁿ | n ∈ ℵ}
5. nenhuma das respostas anteriores

O primeiro passo realizado pelo algoritmo de Exclusão de Produções da Forma A → B é a construção dos fechos para cada uma das variáveis presentes na gramática. Considerando a gramática livre de contexto a seguir, qual conjunto é o fecho da variável A?

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

1. Ø
2. {C}
3. {C, E}
4. {B, C, E}
5. {B, C, E, F}

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

G = ({S, A, B}, {a, b}, P, S)
P = {S → aAB
     A → bBb
     B → A | ε}

Observe a gramática a seguir.

G = ({S, A, B}, {a, b}, P, S)
P = {S   → aAbba
     aAb → aabbbA | ab
     bAb → bbA
     bAa → Bbaa
     bB  → Bb
     aB  → aA}

Sobre essa gramática, assinale a alternativa correta:

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