CFG, PDA & context-free languages

15 questions over all of Phase 3, weighted towards classification and closure as in GATE.

1. MCQ · 1 mark

   L(S → aSbb | abb) is:

   1. { aⁿb²ⁿ : n ≥ 1 }
   2. { aⁿbⁿ }
   3. { a²ⁿbⁿ }
   4. a⁺b⁺
2. MSQ · 2 marks

   Which grammars are ambiguous?

   1. S → SS | a | b
   2. S → aSb | ab
   3. E → E + E | id
   4. S → aS | bS | ε
3. NAT · 1 mark

   Derivation steps in CNF for a string of length 12?

   Write your answer before opening the key.

4. MSQ · 1 mark

   Which variables are useless in S → AB | a, A → a, B → BC, C → c?

   1. S
   2. A
   3. B
   4. C
5. MCQ · 2 marks

   Which language can be accepted by a DPDA by empty stack?

   1. a*
   2. { aⁿbⁿ : n ≥ 1 }
   3. { a, aa }
   4. (ab)*
6. MSQ · 2 marks

   Which are true?

   1. Regular ⊊ DCFL
   2. DCFL ⊊ CFL
   3. NPDA and DPDA accept the same languages
   4. Every DCFL has an unambiguous grammar
7. MCQ · 1 mark

   The PDA obtained from a CFG simulates:

   1. rightmost derivations
   2. leftmost derivations
   3. CYK
   4. shortest derivations
8. MSQ · 2 marks

   CFLs are closed under:

   1. reversal
   2. complement
   3. homomorphism
   4. intersection with regular sets
9. MCQ · 2 marks

   L₁ = { aⁿbⁿcᵐ }, L₂ = { aᵐbⁿcⁿ }. L₁ ∩ L₂ is:

   1. regular
   2. DCFL
   3. CFL, not DCFL
   4. not CFL
10. MSQ · 1 mark

    For arbitrary CFGs, which have algorithms?

    1. membership
    2. emptiness
    3. ambiguity
    4. equivalence
11. NAT · 1 mark

    CYK table cells for n = 7?

    Write your answer before opening the key.

12. MCQ · 2 marks

    To show aⁿbⁿcⁿ is not a CFL, the key fact is:

    1. |vwx| ≤ p so the window misses one of the three blocks
    2. |xy| ≤ p
    3. v must be in the a’s
    4. w must be empty
13. MSQ · 2 marks

    Which are CFL but not DCFL?

    1. { wwᴿ }
    2. { aⁱbʲcᵏ : i = j or j = k }
    3. { aⁿbᵐcⁿ }
    4. complement of { ww }
14. MCQ · 2 marks

    { aⁱbʲcᵏ : i < j < k } is:

    1. regular
    2. DCFL
    3. CFL, not DCFL
    4. not CFL
15. MCQ · 1 mark

    { aⁿbⁿ : n ≤ 50 } is:

    1. regular
    2. DCFL, not regular
    3. CFL, not DCFL
    4. not CFL