Push-down automata

A PDA is a finite automaton with an unbounded stack: moves read a symbol or ε, look at the top, and replace it by a string. Acceptance by final state and by empty stack are equivalent for NPDAs; empty-stack DPDAs accept only prefix-free languages, so DCFLs use final state. DPDAs forbid competing moves; Regular ⊊ DCFL ⊊ CFL (wwᴿ separates). CFGs ↔ PDAs: expand/match simulation of leftmost derivations, and [pXq] triples back.

1. MCQ

   Which language needs nondeterminism in a PDA?

   1. { aⁿbⁿ }
   2. { wcwᴿ }
   3. { wwᴿ }
   4. { aⁿbᵐ : n ≥ m }
2. MSQ

   Which are true?

   1. Every regular language is a DCFL
   2. Every DCFL is unambiguous
   3. DPDA = NPDA in power
   4. Final-state and empty-stack NPDAs are equivalent
3. NAT

   ID (q, ab, AZ). Move δ(q, a, A) ∋ (p, BBA). Stack size after the move?

   Write your answer before opening the key.

4. MCQ

   A PDA accepting by empty stack ends with input read in a non-accepting state with Z on the stack. It:

   1. accepts
   2. rejects
   3. loops
   4. depends on F
5. MSQ

   Which are CFL but not DCFL?

   1. { wwᴿ }
   2. { aⁿbⁿ } ∪ { aⁿb²ⁿ }
   3. { aⁱbʲcᵏ : i = j or j = k }
   4. { aⁿbⁿ }
6. MCQ

   In CFG → PDA, the move for terminal a is:

   1. (q, ε, a) → (q, ε)
   2. (q, a, a) → (q, ε)
   3. (q, a, Z) → (q, aZ)
   4. (q, a, A) → (q, a)
7. NAT

   Empty-stack DPDAs can accept a language L only if L is prefix-free. How many strings of { a, ab, b, ba } must be removed to make it prefix-free (remove as few as possible)?

   Write your answer before opening the key.

8. MCQ

   Which is a DCFL?

   1. { wwᴿ }
   2. { aⁿbᵐcⁿ }
   3. { aⁱbʲcᵏ : i = j or j = k }
   4. { aⁿbⁿcⁿ }