Drill: regular, DCFL, CFL or not CFL?

1. Is { ww } context-free?
   Stuck? Peek at 3.4.3 Pumping lemma for CFLs

   • L CFL ⇒ ∃p ∀z ∈ L, |z| ≥ p: z = uvwxy, |vwx| ≤ p, |vx| ≥ 1, uvⁱwxⁱy ∈ L ∀i ≥ 0. p = 2ᵏ (CNF, k variables).
   • Non-CFL: aⁿbⁿcⁿ, ww, aⁿbᵐcⁿdᵐ, #a=#b=#c, a^{n²}, a^{prime}, aⁱbʲcᵏ (i<j<k).
   • Unary CFL ⇒ regular. Complement of ww is a CFL.

   Read lesson 3.4.3

2. Are CFLs closed under intersection?
   Stuck? Peek at 3.4.1 Closure properties of CFLs and DCFLs

   • CFL closed: ∪, concat, *, reversal, h, h⁻¹, substitution, ∩R, −R. Not: ∩, complement, difference.
   • DCFL closed: complement, ∩R, ∪R, −R, h⁻¹. Not: ∪, ∩, concat, *, reversal, h.
   • Counterexample: aⁿbⁿcᵐ ∩ aᵐbⁿcⁿ = aⁿbⁿcⁿ. Non-CFL proof: L ∩ R non-CFL ⇒ L non-CFL.

   Read lesson 3.4.1

3. Is { w x wᴿ : w, x ∈ Σ⁺ } regular?
   Stuck? Peek at 2.4.4 Drill: regular or not?

   • Bounded fact (mod, flag, last k, capped count, bounded difference) ⇒ regular.
   • Exact comparison of two unbounded counts, ww, wwᴿ, squares, primes, 2ⁿ ⇒ not regular.
   • Finite ⇒ regular. Unary: regular ⇔ lengths eventually periodic.
   • wxwᴿ, wxw (x ∈ Σ⁺) regular. #ab = #ba regular. ww over one letter regular.

   Read lesson 2.4.4

The single most frequent TOC question type on GATE: “Which of the following languages is context-free but not regular?” or “… is a DCFL?”. Speed comes from a ladder of questions you ask in order, plus a memory bank of the standard examples.

Classify { aⁱbʲcᵏ : i = j + k }.

Prediction check

DCFL (not regular). Push a’s; pop one a per b, then one per c; accept if the stack is back to Z₀ exactly at the end. No guessing, one count matched against a sum.

The ladder

1. Finite or only bounded facts? → regular.
2. One comparison of counts that a stack can do in one left-to-right sweep (nested or sequential, never crossing)? → CFL. If you can tell when to switch from pushing to popping without guessing → DCFL.
3. Two independent comparisons (three equal counts), crossing matches, copies (ww), squares/primes → not a CFL.

Signals of “CFL but not DCFL”

• Unmarked middle: wwᴿ, palindromes.
• Union of two different comparisons: aⁱbʲcᵏ with i = j or j = k; aⁿbⁿ ∪ aⁿb²ⁿ.
• Non-deterministic choice of what to compare: { aⁱbʲ : i ≠ j } is still a DCFL (just compare), but { aⁱbʲcᵏ : i ≠ j or j ≠ k } is a CFL not DCFL.

Signals of “DCFL”

A marker or a fixed order tells the machine when to switch: wcwᴿ, aⁿbⁿ, aⁿbᵐcⁿ, aⁱbʲcᵏ with i = j + k, balanced brackets, #a = #b, { aⁱbʲ : i ≠ j }, { aⁱbʲ : i ≥ j }.

Signals of “not CFL”

aⁿbⁿcⁿ, #a = #b = #c, ww (|w| unrestricted, ≥ 2 symbols), aⁿbᵐcⁿdᵐ, aⁱbʲcᵏ with i < j < k, a^{n²}, a^{2ⁿ}, a^{prime}, { aⁿbⁿ… } with a product (aᵐbⁿc^{mn}).

Traps

• { aⁿbⁿcᵐ } is a DCFL; { aⁿbⁿcⁿ } is not even a CFL.
• { wwᴿ : |w| ≤ 10 } is finite ⇒ regular.
• { aⁿbⁿ : n ≥ 0 } ∪ { aᵐbⁿ : m ≠ n } = a*b* ⇒ regular.
• { ww : w ∈ a* } = (aa)* ⇒ regular.
• { aⁿ b aⁿ } is DCFL; { aⁿbⁿ } ∩ R is CFL for regular R.

Putting it together

• Ask the ladder in order: bounded? one deterministic comparison? one guessed comparison? two comparisons?
• “or” usually means CFL not DCFL; “and” usually means not CFL.
• Watch for finite bounds and unions that collapse.

                 REGULAR      DCFL            CFL (not DCFL)          NOT CFL
                 a*b*         aⁿbⁿ            wwᴿ                     aⁿbⁿcⁿ
                 (ab)ⁿ        wcwᴿ            aⁿbⁿ ∪ aⁿb²ⁿ            ww
                 aⁿbⁿ,n≤9     aⁿbᵐcⁿ          aⁱbʲcᵏ: i=j or j=k      aⁿbᵐcⁿdᵐ
                 wxwᴿ         #a = #b         complement of ww        a^{n²}, a^{prime}
                              aⁱbʲ, i≠j                               #a = #b = #c

Phase 3 complete: one stack gives CFLs, determinism gives DCFLs, and two comparisons break even CFLs. Phase 4 removes the stack’s restriction: an endless tape the machine can read and write anywhere — the Turing machine, as powerful as any computer.

1. MCQ

   Which is a CFL but not a DCFL?

   1. { aⁿbⁿ }
   2. { wwᴿ }
   3. { wcwᴿ }
   4. { aⁿbⁿcⁿ }
2. MSQ

   Which are DCFLs?

   1. { aⁱbʲ : i ≠ j }
   2. { aⁱbʲcᵏ : i = j + k }
   3. { aⁱbʲcᵏ : i = j or j = k }
   4. { w : #a = #b }
3. MSQ

   Which are not context-free?

   1. { aⁿbⁿcᵐdᵐ }
   2. { aⁿbᵐcⁿdᵐ }
   3. { aᵐbⁿc^{mn} }
   4. { a^{2ⁿ} }
4. MCQ

   { aⁿbⁿ : n ≥ 0 } ∪ { aᵐbⁿ : m ≠ n } is:

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

   { aⁿ b aⁿ : n ≥ 0 } is:

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

• classification ladder
• CFL-not-DCFL signals
• DCFL signals
• non-CFL signals

1. Classify { aⁱbʲcᵏ : i = j or j = k }.
   Reveal answer

   CFL, not DCFL (inherently ambiguous).
2. Classify { aⁿbᵐcⁿ }.
   Reveal answer

   DCFL.
3. Classify { aⁿbᵐcⁿdᵐ }.
   Reveal answer

   Not a CFL (crossing).
4. Classify { aⁿbⁿcᵐdᵐ }.
   Reveal answer

   DCFL (two nested pairs in sequence).