Context-free grammars

A CFG has rules A → α with one variable on the left. Derivations build parse trees; trees correspond one-to-one with leftmost and with rightmost derivations. Standard grammars: aⁿbⁿ (S → aSb | ε), palindromes, balanced parentheses, #a = #b (S → aSbS | bSaS | ε), i ≠ j (equal core plus extras), unions, concatenations. A grammar is ambiguous if a string has two parse trees; some languages (aⁱbʲcᵏ, i = j or j = k) are inherently ambiguous.

1. MCQ

   L(S → aSb | aS | ε) is:

   1. { aⁿbⁿ }
   2. { aⁱbʲ : i ≥ j }
   3. { aⁱbʲ : i ≤ j }
   4. a*b*
2. MSQ

   Which strings are in L(S → SS | (S) | ε)?

   1. (()())
   2. )(
   3. ()(())
   4. (()
3. MCQ

   The grammar S → aSa | bSb | a | b is:

   1. ambiguous
   2. unambiguous
   3. not context-free
   4. regular
4. NAT

   With S → aSbb | ε, length of the string derived with 4 applications of S → aSbb?

   Write your answer before opening the key.

5. MCQ

   Which proves ambiguity?

   1. a leftmost and a rightmost derivation of w
   2. two parse trees of w
   3. two grammars for L
   4. a string with a long derivation
6. MSQ

   Which are context-free languages?

   1. { aⁿbⁿ }
   2. palindromes
   3. { aⁿbᵐcᵐdⁿ }
   4. every regular language
7. NAT

   Number of parse trees of id+id+id in E → E+E | id?

   Write your answer before opening the key.

8. MCQ

   S → aSbS | bSaS | ε generates:

   1. palindromes
   2. strings with #a = #b
   3. aⁿbⁿ
   4. (ab)*