CSCD 420 Oct 08 2026

Overview

The lecture develops the pumping lemma as a contradiction method for proving that a language is not regular: assume a DFA with m states exists, choose a suitable string of length at least m, and show that every legal decomposition XYZ can be pumped or shortened to leave the language. Examples include even-length palindromes, strings with more B's than A's, and strings of the form (ab)^n a^k where n > k; course logistics also clarify that the upcoming exam excludes pumping-lemma material.

Key takeaways

For an m-state DFA, any accepted string of length at least m forces a repeated state, yielding a nonempty cycle segment Y in a decomposition XYZ.
A nonregularity proof must handle every legal split with |XY| ≤ m and |Y| ≥ 1, not merely demonstrate that one particular split fails.
For even-length palindromes, a^m b^m b^m a^m forces Y into the initial A-block; pumping Y adds unmatched A's and destroys the palindrome.
For strings with more B's than A's, a^m b^(m+1) is an effective boundary string because pumping an A-only prefix immediately removes the required B surplus.
When pumping upward is inconvenient, pumping downward with i = 0 can expose violations; for (ab)^n a^k with n > k, deletion may break alternation or eliminate the strict inequality.
Upcoming exam coverage stops at regular grammars and excludes pumping-lemma material, while the assessment favors applied problem solving over definition recall.

Chapters

0:00 Homework, Exam Scope, and Assignment Feedback

The quarter's homework file is available, and students may work ahead because lecture coverage has historically preceded related assignments.
The next assignment is due Wednesday; a study guide is expected the following day for an exam one week later.
The exam covers material through regular grammars and excludes the pumping lemma; questions will emphasize concept explanations and problem solving over memorization.
Feedback on Homework 1 may be delayed because of illness and office relocation after first-floor flood damage; corrections or resubmissions may be considered to prevent one issue carrying into multiple assignments.

4:29 Pumping Lemma: A DFA Cycle Forces Repeated Strings

To prove a language is not regular, assume an accepting DFA with m states exists and examine a string in the language with at least m characters.
The DFA must revisit a state, creating a cycle; split the accepting path into X before the cycle, Y for one traversal, and Z after it.
Because the cycle can be traversed repeatedly, XY^iZ must remain accepted for any nonnegative pumping count i if the DFA recognizes the language.
A DFA cycle consumes at least one input character, so Y cannot be empty.

10:12 The Pumping Lemma as a Two-Player Proof Game

Player One chooses m, the number of states in a hypothetical accepting DFA; the proof must work for every possible m.
Player Two chooses a language member W of length at least m, then Player One chooses XYZ subject to |XY| ≤ m and |Y| ≥ 1.
Player Two wins by finding a pumping count i that makes XY^iZ fall outside the language for every legal decomposition.
A single failed choice of W or i does not establish regularity; the argument must give Player Two a successful response for all of Player One's choices.

15:30 Even-Length Palindromes: Choose a String with an A-Only Prefix

For the language {ww^R}, choose W = a^m b^m b^m a^m, an even-length palindrome that must be accepted if the language is regular.
The first m characters are all A's, ensuring the cycle required by an m-state DFA occurs entirely within that A-block.
The choice of a uniform A-prefix restricts every legal X and Y to A's, making it possible to predict how pumping changes the string.
The string scales with the hypothetical DFA size: if m = 17, the construction begins with 17 A's and still belongs to the palindrome language.

20:03 Pumping the Palindrome Prefix Breaks Its Mirror Structure

Since |XY| ≤ m and |Y| ≥ 1, Y consists of at least one A from the initial block and contains no B's.
Set i = 2 to add one extra copy of Y while leaving the trailing blocks unchanged, producing a^m+|Y| b^m b^m a^m.
The added A's have no matching additions in the mirrored final A-block, so the pumped string is no longer an even-length palindrome.
For the illustrative case m = 3 and Y = aaa, pumping once more yields six initial A's while the remaining blocks retain their original lengths.

28:18 Choosing Robust Strings and Why Regular Languages Pass the Test

A strong pumping-lemma string narrows the legal decompositions: here, every possible Y contains only A's.
For a regular language, pumping a valid DFA cycle continues to produce strings in the language, so the final contradiction step cannot succeed.
The method applies to many assigned nonregular-language proofs, but success depends on choosing a string that exposes the language's structural constraint.
Not every nonregular language has an easy pumping-lemma proof; some require more unusual arguments.

35:09 More B's Than A's: Pump a Boundary String

For strings over {a,b} with more B's than A's, choose a^m b^(m+1), placing the string just one B inside the language's boundary.
Putting all A's first ensures that any legal Y within the first m characters consists only of A's.
Pumping Y once adds at least one A without adding any B, so the resulting string has at least as many A's as B's and is outside the language.
A choice such as a^m b^(2m) could also work, but it may require pumping many times; the boundary choice makes the contradiction immediate.

40:55 The Language (ab)^n a^k: Choose Nearly Equal Parameters

For L = {(ab)^n a^k : n > k ≥ 0}, choose (ab)^(m+1) a^m, where n exceeds k by only one.
The cycle must occur within the first m characters, inside the alternating (ab) portion, so removing Y with i = 0 is the useful strategy.
The string is deliberately near the condition n > k boundary, meaning a small deletion can eliminate the strict inequality.
Unlike the earlier examples, Y may contain both A's and B's, so its possible forms need further case analysis.

45:28 Pumping Down in Four Cases and Closing the Proof

Classify Y by its first and last characters: it can start and end with A, start with A and end with B, start with B and end with A, or start and end with B.
If Y is a single A, deleting it creates consecutive B's, which strings in (ab)^n a^k do not permit.
For longer deletions, the cases either break the alternating pattern or remove enough AB pairs that n is no longer strictly greater than k.
Case analysis must cover every legal Y; office hours were offered immediately and from 1 to 2, with the topic continuing the next day.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Chris Cain.