a) Defina uma gramática de estrutura de frase.
b) O que significa uma seqüência ser derivável de uma seqüência w por uma gramática de estrutura de frase G ?

Passo 1

O enunciado pede dois pontos:
a) Definir o que é uma gramática de estrutura de frase.
b) Explicar o que significa, para uma gramática de estrutura de frase G, que uma sequência seja derivável de outra sequência w.

Passo 2

Uma gramática de estrutura de frase é um sistema formal
G = (V, \Sigma, P, S)
onde:
V é um conjunto finito de símbolos não-terminais (variáveis).
\Sigma é um conjunto finito de símbolos terminais, com V\cap\Sigma=\varnothing.
P é um conjunto finito de regras de produção, cada uma da forma \alpha \to \beta com \alpha\in (V\cup\Sigma)^+ contendo ao menos um símbolo de V, e \beta\in (V\cup\Sigma)^*.
S\in V é o símbolo inicial.

Passo 3

Dizemos que, em uma gramática G, uma sequência x é derivável de uma sequência w (escrevemos w \Rightarrow_G^* x) se existe uma cadeia finita de aplicações de produções em P que transforma w em x. Formalmente,
u\Rightarrow_G v em um passo se u = \gamma\,\alpha\,\delta e existe \alpha\to\beta em P tal que v = \gamma\,\beta\,\delta.
w\Rightarrow_G^* x significa que há n\ge0 e sequências w_0, w_1,\dots,w_n com w_0 = w, w_n = x e w_{i}\Rightarrow_G w_{i+1} para todo 0\le i<n.

Resposta

a) Uma gramática de estrutura de frase é um 4-tuplo
G = (V,\Sigma,P,S)
onde V é o conjunto de não-terminais, \Sigma o de terminais, P o de produções \alpha\to\beta com \alpha contendo pelo menos um não-terminal, e S o símbolo inicial.
b) Uma sequência x é derivável de w por G (escrevemos w\Rightarrow_G^* x) se existe uma sucessão finita de aplicações das regras de P que leva w até x.