Drill: regular or not?

1. Why does |xy| ≤ p matter when proving aⁿbⁿ non-regular?
   Stuck? Peek at 2.4.3 Pumping lemma for regular languages

   • L regular ⇒ ∃p ∀w ∈ L, |w| ≥ p, ∃ xyz: |xy| ≤ p, |y| ≥ 1, ∀i ≥ 0: xyⁱz ∈ L. p = #states.
   • Game: they pick p and split; you pick w and i. Beat every split.
   • Standard picks: aᵖbᵖ; a^{p²}; aᵖbaᵖb (ww); prime q ≥ p+2 with i = q+1.
   • Necessary, not sufficient. Finite languages pass vacuously.

   Read lesson 2.4.3

2. Is a regular language closed under reversal?
   Stuck? Peek at 2.4.1 Closure properties of regular languages

   • Closed: ∪ ∩ − complement, concat, *, ⁺, reversal, homomorphism, inverse homomorphism, quotient (by any language), prefix, suffix, substring, substitution, finite ∪/∩.
   • Not guaranteed: infinite ∪/∩, subset, superset.
   • Prove non-regular: L ∩ R non-regular (R regular) ⇒ L non-regular.

   Read lesson 2.4.1

3. Minimal DFA states for binary numbers divisible by 6?
   Stuck? Peek at 1.1.3 DFA design patterns

   Language (|w| = k pattern)	Minimal states
   starts with w	k + 2
   contains w / ends with w	k + 1
   |x| ≡ r mod n	n
   |x| = k, |x| ≤ k	k + 2
   |x| ≥ k	k + 1
   #a mod m and/or #b mod n	m·n (typical)
   binary value ≡ 0 mod k, k odd	k
   binary ÷ 2ʲ	j + 1
   k-th symbol from start fixed	k + 2

   Divisibility update: r ← (base·r + digit) mod k.

   Read lesson 1.1.3

In the exam you don’t write pumping proofs. You see a list of 4 languages and must tick the regular ones in about a minute. The skill is intuition about memory: can a machine with a fixed number of states keep track of what is needed? This lesson gives you rules of thumb, then the traps where intuition lies.

Regular or not: L = { w x wᴿ | w, x ∈ {a,b}⁺ }? (wᴿ is w reversed.)

Prediction check

Regular! Choose w to be just the first symbol: if a string starts and ends with the same symbol and has length ≥ 3, take w = that symbol and x = the middle. Conversely any such string starts and ends with the same symbol. So L = a(a+b)⁺a + b(a+b)⁺b. The famous trap: “wᴿ” looks like it needs memory, but x can absorb everything.

Rule 1 — bounded facts are regular

Counts modulo a constant, the last k symbols, whether a pattern has appeared, a count capped at a constant (“at least 3 a’s”, “at most 5”): all regular.

Rule 2 — unbounded comparison is not regular

Comparing two counts (#a = #b, n ≥ m, n = 2m), matching a string with its copy or reverse (ww, wwᴿ with |w| unrestricted), squares, primes, powers of 2: not regular.

Rule 3 — watch for bounds and finite sets

• { aⁿbⁿ : n ≤ 100 } is finite ⇒ regular.
• { aⁿbᵐ : n, m ≥ 0 } — no relation ⇒ a*b*, regular.
• { aⁿbᵐ : n + m is even } — only parity ⇒ regular.
• { aⁿbᵐ : n ≡ m (mod 3) } ⇒ regular (track (n − m) mod 3).

Rule 4 — unary languages

Over a one-letter alphabet, L is regular iff the set of lengths is eventually periodic (from some point on, repeats with a fixed period). a^{2n}, a^{3n+1}, lengths ≥ 7: regular. Squares, primes, powers of 2, Fibonacci lengths: not regular.

Rule 5 — the x-absorbs-it trap

• { wxwᴿ : w, x ∈ Σ⁺ } regular (first = last symbol, length ≥ 3).
• { wxw : w, x ∈ Σ⁺ } regular by the same idea (first symbol reappears at the end).
• { wwᴿx : … } and { xwwᴿ } with w ∈ Σ⁺: careful — these require an even palindrome somewhere and are NOT regular in general unless x can absorb; {wwᴿ : w ∈ Σ*} itself is not regular.
• { ww : w ∈ {a}* } = (aa)* — regular (unary!).

Rule 6 — the comparison that a DFA can still do

“#ab = #ba as substrings” is regular: in any binary string, the number of “ab” and “ba” occurrences differ by at most 1, and they are equal exactly when the first and last symbols are the same (or the string is short). Intuition can fail; when a weird comparison appears, look for such hidden structure.

Putting it together

• Ask what fact must be carried: bounded → regular; an exact comparison of unbounded counts → not regular.
• Finite languages and eventually periodic unary sets are regular.
• A free middle x often absorbs the hard part (wxwᴿ, wxw).

         REGULAR                                  NOT REGULAR
 a*b*                                     aⁿbⁿ
 aⁿbᵐ, n+m even                           aⁿbᵐ, n ≥ m
 #a ≡ #b (mod 3)                          #a = #b
 aⁿbⁿ, n ≤ 1000  (finite)                 aⁿbⁿcⁿ
 w x wᴿ  (w,x ∈ Σ⁺)                       w wᴿ
 ww over {a}  = (aa)*                     ww over {a,b}
 a^{2n+1}                                 a^{n²}, a^{2ⁿ}, a^{prime}
 #ab = #ba                                aⁿ bᵐ cⁿ⁺ᵐ

Phase 2 complete: regular languages have five equivalent descriptions, strong closure, algorithms for every question, and a clear boundary. Beyond that boundary are aⁿbⁿ, balanced brackets, palindromes. Phase 3 gives the machine its first unbounded memory — a stack — and meets the grammars that describe these languages.

1. MSQ

   Which are regular?

   1. { aⁿbᵐ : n, m ≥ 0 }
   2. { aⁿbⁿ : n ≥ 0 }
   3. { aⁿbᵐ : n ≡ m (mod 2) }
   4. { aⁿbⁿ : 0 ≤ n ≤ 10 }
2. MCQ

   { w x wᴿ : w, x ∈ {0,1}⁺ } is:

   1. not regular
   2. regular
   3. finite
   4. empty
3. MSQ

   Over {a}, which are regular?

   1. { a^{n²} }
   2. { a^{3n+2} }
   3. { aⁿ : n ≥ 100 }
   4. { a^{2ⁿ} }
4. MCQ

   { w ∈ {a,b}* : |w|ₐ = 2|w|_b } is:

   1. regular
   2. not regular
   3. finite
   4. equal to Σ*
5. MCQ

   { w ∈ {a,b}* : #(ab) = #(ba) } (occurrences as substrings) is:

   1. regular
   2. not regular
   3. finite
   4. empty

• regular-or-not intuition
• eventually periodic (unary)
• bounded difference
• absorbing middle (wxwᴿ)

1. Is { w x wᴿ : w, x ∈ Σ⁺ } regular?
   Reveal answer

   Yes — same first and last symbol, length ≥ 3.
2. Is { aⁿbᵐ : n ≡ m mod 3 } regular?
   Reveal answer

   Yes.
3. When is a unary language regular?
   Reveal answer

   When its set of lengths is eventually periodic.
4. Is { w : #ab = #ba } regular?
   Reveal answer

   Yes.
5. Is { aⁿbᵐ : n ≠ m } regular?
   Reveal answer

   No (complement ∩ a*b* = aⁿbⁿ).

• Regular-or-not in 10 seconds: (1) finite? → regular. (2) only remainders/flags/last-k/caps? → regular. (3) two unbounded quantities compared exactly? → not regular. (4) a free middle x? → it probably absorbs the hard part → regular.