Quiz 9

Consider the context-free grammar ({S}, {(,)}, P, S), where P contains the following productions:

  S → (S)S
  S → ε

1. (1p) Which of the following expressions are well-formed sequences of derivations for the grammar above?

   1. S ⇒ (S)S ⇒ (S) ⇒ ()

   2. S ⇒ ((S)S)S ⇒ ((S)) ⇒ (())

   3. S ⇒ (S)S ⇒ ((S)S)S ⇒ (()S)S ⇒ (())S

   4. S ⇒ ε

   5. S ⇒ (())()

2. (1p) Which of the following expressions are well-formed sequences of left-most derivations for the grammar above?

   1. S ⇒_lm (S)S ⇒_lm (S) ⇒_lm ()

   2. S ⇒_lm ((S)S)S ⇒_lm ((S)) ⇒_lm (())

   3. S ⇒_lm (S)S ⇒_lm ((S)S)S ⇒_lm (()S)S ⇒_lm (())S

   4. S ⇒_lm ε

   5. S ⇒_lm (())()

3. (1p) Which of the following strings are members of the language defined by the grammar above?

   1. (())()()

   2. (()(()()

   3. (((())))

   4. ))))((((

   5. (())()(())

4. (1p) Which of the following strings are right-sentential forms for the grammar above?

   1. ε

   2. SS

   3. ((S))()

   4. (()S)()

   5. (((())))

5. (1p) Consider the (unique) parse tree for the grammar above that has (())() as its yield. How many leaves does this tree have?