Where you are in the story
Phase 3 gave machines one stack. Phase 4 gives them a tape they can read, write and move along freely. Before the jump, make sure the stack world is solid — the containment chain you will build next starts with Regular ⊂ DCFL ⊂ CFL.
Previous phase in pictures
Grammar ↔ stack machine
The hierarchy so far
A stack run
States: q0, q1, q2
Transitions: q0>q0: a,Z/AZ | a,A/AA; q0>q1: b,A/ε; q1>q1: b,A/ε; q1>q2: ε,Z/Z; q0>q2: ε,Z/Z
Closure, side by side
| operation | Reg | DCFL | CFL |
|---|---|---|---|
| ∪ | ✓ | ✗ | ✓ |
| ∩ | ✓ | ✗ | ✗ |
| complement | ✓ | ✓ | ✗ |
| concat / star | ✓ | ✗ | ✓ |
| ∩ regular | ✓ | ✓ | ✓ |
Where one stack fails
Carry these forward
What makes a grammar context-free?
One variable on the left of every rule. (3.1.1)
When is a grammar ambiguous?
Some string has two parse trees. (3.1.3)
CNF derivation steps for length n?
2n − 1. (3.2.2)
PDA 7-tuple?
(Q, Σ, Γ, δ, q₀, Z₀, F). (3.3.1)
Empty-stack DPDAs accept which languages?
Only prefix-free DCFLs. (3.3.2)
Standard CFL that is not a DCFL?
wwᴿ. (3.3.3)
Are CFLs closed under complement?
No; DCFLs are. (3.4.1)
CYK time?
O(n³ · |G|). (3.4.2)
CFL pumping window?
|vwx| ≤ p, |vx| ≥ 1. (3.4.3)
Is ww context-free?
No (its complement is). (3.4.4)
Quick refresher
- MCQ
Which is CFL but not DCFL?
- aⁿbⁿ
- wwᴿ
- wcwᴿ
- a*b*
- MSQ
Which are not CFLs?
- aⁿbⁿcⁿ
- ww
- aⁿbᵐcⁿ
- a^{prime}
- NAT
CNF steps for a string of length 6?
Write your answer before opening the key.
- MCQ
CFLs are closed under:
- intersection
- complement
- Kleene star
- difference
What the next phase adds
Answer Vault
Reveal answers when you’re ready
- B — Middle must be guessed.
- A: DCFL.
- C: DCFL.
- D: Regular.
- ABD — Standard non-CFLs.
- C: DCFL.
- 11 — 2n − 1.
- C — Grammar S → S₁S | ε.
- A: No.
- B: No.
- D: No.