a) Defina uma gramática de estrutura de frase.
b) O que significa uma seqüência ser derivável de uma seqüência
por uma gramática de estrutura de frase
?
b) O que significa uma seqüência ser derivável de uma seqüência
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 , que uma sequência seja derivável de outra sequência
.
a) Definir o que é uma gramática de estrutura de frase.
b) Explicar o que significa, para uma gramática de estrutura de frase
Passo 2
Uma gramática de estrutura de frase é um sistema formal
onde:
— é um conjunto finito de símbolos não-terminais (variáveis).
— é um conjunto finito de símbolos terminais, com
.
— é um conjunto finito de regras de produção, cada uma da forma
com
contendo ao menos um símbolo de
, e
.
— é o símbolo inicial.
—
—
—
—
Passo 3
Dizemos que, em uma gramática
, uma sequência
é derivável de uma sequência
(escrevemos
) se existe uma cadeia finita de aplicações de produções em
que transforma
em
. Formalmente,
— em um passo se
e existe
em
tal que
.
— significa que há
e sequências
com
,
e
para todo
.
—
—
Resposta
a) Uma gramática de estrutura de frase é um 4-tuplo
onde
é o conjunto de não-terminais,
o de terminais,
o de produções
com
contendo pelo menos um não-terminal, e
o símbolo inicial.
b) Uma sequência
é derivável de
por
(escrevemos
) se existe uma sucessão finita de aplicações das regras de
que leva
até
.