Question

Seja a linguagem gerada pela gramática S -> ZT | aWd; Z-> aZb | ab; T -> cTd | cd; W -> aWd | R. Esta gramática gera a linguagem {a^m b^n c^n d^m / m, n > 0} .

Considere cadeias na forma a^n, b^n, c^n, d^n, n > 0. Assinale a resposta correta sobre o número máximo de árvores de derivação possíveis de se obter para estas cadeias com a gramática acima.

Escolha uma:

a. Somente duas para cada cadeia. Existem duas derivações mais à esquerda diferentes para cada cadeia a^n, b^n, c^n, d^n, n > 0 .

b. Nenhuma árvore, pois as cadeias não pertencem a linguagem gerada pela gramática.

c. "n" árvores de derivação diferentes. Para cada cadeia a^n, b^n, c^n, d^n, existe uma árvore de derivação para cada aplicação de regra que coloca "a" na esquerda e "d" mais à direita.

d. Para cada cadeia existem duas árvores diferentes, pois é possível fazer derivações mais à direita e mais à esquerda com esta gramática.

e. Somente uma para cada cadeia, pois somente é possível uma derivação mais à esquerda para cada uma destas cadeias.

Answer 1

A. Somente duas para cada cadeia. Existem duas derivações mais à esquerda diferentes para cada cadeia a^n, b^n, c^n, d^n, n > 0. 

Answer 2

Somente duas para cada cadeia. Existem duas derivações mais à esquerda diferentes para cada cadeia a^n, b^n, c^n, d^n, n > 0.