Quiz 9

If you cannot access Canvas and submit your answers via email, please only give the answers (a number or a list of numbers), and no motivating arguments.

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?