Ybadoo - Soluções em Software Livre
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 = {AV=E
     ET+E | T-E | T
     TF*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}.

Questão 03

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

SASb
A → a
  1. {ancb | n ∈ ℵ}
  2. {acbn | n ∈ ℵ}
  3. {ancnb | n ∈ ℵ}
  4. {ancbn | n ∈ ℵ}
  5. nenhuma das respostas anteriores

Questão 04

O primeiro passo realizado pelo algoritmo de Exclusão de Produções da Forma AB é 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
     CE | xA
     DEF | Axy
     EF | xyz | B
     FDF | 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
     BA | ε}

Questão Extra

Observe a gramática a seguir.

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

Sobre essa gramática, assinale a alternativa correta:

  1. É irrestrita e aceita a linguagem {anb2n+1an | n ≥ 1}.
  2. É irrestrita e aceita a linguagem {anb2nan | n ≥ 1}.
  3. É sensível ao contexto e aceita a linguagem {anb2n+1an | n ≥ 1}.
  4. É sensível ao contexto e aceita a linguagem {anb2nan | n ≥ 1}.
  5. É livre de contexto e aceita a linguagem {anb2n+1an | n ≥ 1}.