Copyright © 2007 Gradiance Corporation.

Gradiance Online Accelerated Learning

Parse Trees --- Additional Questions

---

---

1.	Consider the grammar G: S → SS, S → ab Which of the following strings is a word of L(G) AND is the yield of one of the parse trees for grammar G in the figure below?

a)	ababab
b)	SababSabS
c)	ababababab
d)	abababababababab

2.	Consider the grammar G: S → abS, S → ab Which of the following strings is a word of L(G) AND is the yield of one of the parse trees for grammar G in the figure below?

a)	abababS
b)	ababababab
c)	abababababab
d)	ababababababab

3.	Consider the grammar: S → SS, S → ab Identify in the list below the one set of parse trees which includes a tree that is NOT a parse tree of this grammar?

a)	{(e)}
b)	{(b),(d)}
c)	{(c),(f)}
d)	{(d),(f)}

4.	The parse tree below represents a leftmost derivation according to the grammar S → AB, A → aS|a, B → bA Which of the following is a left-sentential form in this derivation?

a)

aaBba

b)

aSbA

c)

AbA

d)

aaBB