CSCD 420 Oct 07 2026

Overview

Chris Cain connects regular grammars to finite automata, then introduces the pumping lemma as a way to prove that languages such as {aⁿbⁿ | n ≥ 0} are not regular. The lecture uses the pigeonhole principle to explain why a DFA with finitely many states must revisit a state on sufficiently long inputs, creating a loop whose repeated input can be tested against the language.

Key takeaways

A right-linear grammar places its single nonterminal at the right end of productions, while a left-linear grammar places it at the left and constructs strings in reverse order.
The language {aⁿbⁿ | n ≥ 0} is not regular because a finite-state machine cannot retain an unbounded count of the initial a symbols and compare it with the later b symbols.
In a DFA with M states, any input path longer than M symbols must revisit a state, creating a nonempty loop by the pigeonhole principle.
The pumping lemma decomposes sufficiently long accepted strings as xyz, with |xy| ≤ M, |y| ≥ 1, and xyⁱz in the language for every i ≥ 0.
A repeatable cycle on an accepting path can generate infinitely many strings; a DFA with no cycles accepts only a finite language.

Chapters

0:00 Converting Right-Linear Grammar Productions into NFA Transitions

A regular grammar is consistently left-linear or right-linear, with at most one nonterminal in each production.
For a right-linear production, terminals before the nonterminal become a sequence of transitions leading to the state named by that nonterminal.
A production ending in terminals with no nonterminal leads to a final state; multiple terminals require intermediate states between transitions.

5:52 Building a Right-Linear Grammar for aa b* a

The example language is aa b* a, where the star applies only to b because no parentheses include other symbols.
A grammar can generate the fixed initial aa, loop on b any number of times, and finish with a.
Regular grammar productions may place multiple terminals before a single nonterminal, provided the nonterminal remains at the right for a right-linear grammar.

10:18 Nested Repetition and Left-Linear Grammar Construction

Nested repetition in a regular expression behaves like an outer loop containing an inner loop, so the grammar must represent both repetition levels and their termination choices.
A left-linear grammar builds strings from right to left, starting from the known final symbol and adding preceding symbols through left-side recursion.
For a string ending in a, the construction can account for a variable run of b symbols before the fixed initial symbols.

16:21 Finite Memory, Regular Languages, and the Pigeonhole Principle

A language is regular when a finite amount of memory suffices to process strings of any length; an arbitrary run of b symbols does not require counting.
The pigeonhole principle says that placing n objects into k boxes with n greater than k forces at least one box to contain multiple objects.
With 3 sock colors, 4 blind draws guarantee a matching pair; with 12 birth months, 13 people guarantee a shared birth month.

22:45 Why aⁿbⁿ Requires Unbounded Counting

The language {aⁿbⁿ | n ≥ 0} requires exactly as many b symbols as preceding a symbols, with all a symbols appearing first.
A DFA that loops freely on a symbols and then b symbols would also accept mismatched counts, such as abbb.
Tracking each possible count of a symbols would require an unbounded number of states; bounding n at 1,000 would instead permit a finite, though large, automaton.

29:10 Contradiction Proof: Repeated DFA States Break Count Matching

Assume a DFA with M states accepts exactly {aⁿbⁿ | n ≥ 0}; reading more than M symbols forces a state to repeat by the pigeonhole principle.
On a sufficiently long a-prefix, the repeated state creates a loop that consumes some positive number of a symbols.
Repeating that loop changes the number of a symbols without changing the b-suffix, producing an accepted string with unequal counts and contradicting the language definition.

35:26 Breaking an Accepting DFA Path into X, Y, and Z

A path through a DFA can be split into X, the prefix reaching a repeated state; Y, the loop; and Z, the suffix reaching a final state.
In the four-state illustration, reading more than four symbols forces a repeated state and therefore a loop.
For a path labeled with a symbols, repeating Y adds more a symbols while preserving the route to acceptance, exposing why aⁿbⁿ cannot be recognized by a finite DFA.

40:42 DFA Cycles Distinguish Finite and Infinite Regular Languages

A DFA transition graph with no cycles has only finitely many paths from its start state to final states, so it accepts a finite language.
A cycle that consumes at least one character can be repeated zero, one, or arbitrarily many times, generating infinitely many accepted strings when it lies on an accepting path.
Every infinite regular language therefore has an accepting DFA path with a repeatable, character-consuming cycle.

44:27 Pumping Lemma Conditions for Regular Languages

For an infinite regular language with an accepting DFA of M states, every string w in the language with |w| ≥ M can be decomposed as xyz.
The decomposition must satisfy |xy| ≤ M and |y| ≥ 1, placing a nonempty loop within the first M symbols.
For every integer i ≥ 0, xyⁱz must remain in the language because repeating or removing the loop still follows a valid accepting path.

49:48 Using Pumping to Contradict Regularity and Reviewing DFA Work

To prove a language is not regular, assume it is regular and show that a sufficiently long string has no valid pumping decomposition that keeps every xyⁱz in the language.
The class defers the complete nonregularity proof to the next meeting, after introducing the loop-based structure and its quantifiers.
The closing discussion covers DFA assignment evidence, including automaton diagrams, screenshots, test-driven checks, and recording when state pairs become distinguishable in a table.

Transcript excerpt

0:02 Okay, hopefully everybody is very caffeinated today because we are finishing with this topic and very quickly diving into what is probably the hardest topic of the entire quarter. It's good news that we're going to get it over with. The bad news is it'll take a little while because it is it is pretty challenging. But an intuitive understanding of DFAS and NFAS will help a lot for understanding how to prove something is not regular. But before we dive into that, I just wanted to let people know that I do have to leave a little bit early, not from this class, but from campus today. So if you have questions, I'll have my typical office hours after class, but I'll have to leave by about 1:30 this afternoon. So if you have any questions for me at one point of me

0:50 there at ones so that I can address them before I update that. All right. Last time we were talking about how to take regular grammarss and convert them into NFAS. So remember or recall that regular parameters have to either be left linear or right linear. And that tells you the position of the single non- terminal up to one non- terminal in each of the productions. If it's right linear, then the non- terminal will appear on the right. It's left linear, it will appear on the left. We then went through this process of saying, well, this sequence of terminals that appears, in this case, we're dealing with a right linear grammar. The sequence of terminals that is before is going to be a sequence of transitions

1:39 between states that end up in the state labeled on the right hand side. So if we have a starting state B 0 then we're going to read an A and end up in B1

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

Related notes

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.