Motivation
A finite-state machine reads a word one symbol at a time while remembering only a bounded amount of information. That restriction makes the class of languages it recognizes mathematically clean, and it also marks a boundary: some simple-looking languages need unbounded memory. These notes make both sides precise. We show that three different descriptions, deterministic automata, nondeterministic automata with silent moves, and regular expressions, define the same languages, and then we prove a tool for showing that a language lies outside the class.
Several standard topics are not treated: minimization algorithms and the full uniqueness theory of minimal automata, for instance, are left out, and the distinguishability bound proved below is only the lower-bound half of that theory.
Definitions
Definition 1.2.1
(Alphabets, words and languages)
An alphabet is a finite nonempty set of symbols. A word over is a finite sequence of symbols; denotes the empty word and the set of all words. The length of is written . A language is any subset of . Concatenation of languages is , and with .
The languages (no words) and (exactly the empty word) are different; confusing them is a frequent source of errors in constructions for concatenation and star.
Definition 1.2.2
(DFA)
A deterministic finite automaton is with finite, a total function, and . Define and . Then .
Definition 1.2.3
(NFA with silent moves)
An -NFA is where . For , the -closure is the least set containing and containing every state reachable from a member by -transitions. Put and . The language is .
Concept lensAlgorithmic
Nondeterminism as simulating a set of states
Read an -NFA as a program that maintains the set of states it could currently be in. Each input symbol first moves every member along matching edges and then closes under silent moves. The program has finitely many possible memory contents, namely the subsets, so it is a DFA. The exponential bound is an upper bound on this program's memory; many NFAs need far fewer reachable subsets, as the first worked example below shows in a small case, where only four of eight subsets are reachable.
Definition 1.2.4
(Regular expressions)
Regular expressions over are built from the atoms , and each , using union , concatenation and star . Their languages are , , , , and . The size of an expression counts every atom and every operator occurrence once. A language is regular if it equals for some DFA .
Definition 1.2.5
(Distinguishable words)
Fix a language . Words are distinguishable (by ) if some word satisfies: exactly one of and lies in .
Theorems
Theorem 1.2.6
(Subset construction)
Let be an -NFA with state set . Define with and . Then . In particular every language of an -NFA is regular, and a DFA with at most states suffices.
Proof
(Tracking the set of reachable states)
First we justify that means what one expects: iff some path from to , whose labels are symbols or , spells after deleting the labels. For such paths use only silent moves, which gives . For , a path splits into a path for ending at some , an -step to , and a silent path from to ; induction supplies , so lies in the stated closure, and the converse reads the same decomposition backwards. Next, by induction on , : the base case is the definition of the start state, and the step is the equation . Acceptance by means , which is .
Proof X-ray
Where each hypothesis enters the subset construction
The construction uses finiteness of only to make a legitimate finite state set. Totality of holds because is defined for every set, including the empty set, which becomes a dead state. The key step is the equation : it says the NFA's whole nondeterministic history is summarized by one set, so the future depends only on that set. The proof closes with the definition of as "some member is accepting".
Theorem 1.2.7
(Thompson construction)
For every regular expression there is an -NFA with , with one start state having no incoming transition, one accepting state different from it having no outgoing transition, and at most states.
Proof
(Structural induction on the expression)
Induct on the structure of . For an atom, use two states joined by nothing (), by , or by the letter; this has two states, matching size . For , add a new start with -edges to the two sub-starts and a new accepting state receiving -edges from the two sub-accepting states; this uses states. For , add an -edge from the accepting state of to the start of ; the new start and accepting states are those of and . For , add a new start and accepting with -edges , , and . The no-incoming and no-outgoing properties are preserved by inspection. Correctness uses these properties: a path can enter a sub-machine only at its start and leave only from its accepting state, so every accepting path factors into complete traversals. For union the path takes exactly one branch; for concatenation it traverses then , giving ; for star it makes complete traversals, giving , and the direct edge supplies .
Theorem 1.2.8
(State elimination recurrence)
Let be an NFA without -moves, with states numbered and start state . Let be the set of words labeling paths from to all of whose intermediate states lie in . Then and
Hence , a finite union of languages given by regular expressions.
Proof
(Cutting a path at its occurrences of the pivot state)
The base case is the definition of one-step paths, with the empty path contributing when . For , consider a path from to with intermediate states in . If is never an intermediate state, the word lies in . Otherwise cut the path at the first and last intermediate occurrences of and at every occurrence between them. The initial piece goes from to , each middle piece from to , and the final piece from to , and every piece has intermediates in . This yields the second term; conversely, concatenating such pieces produces a path of the required kind. The recurrence proves correctness only; the expressions may grow very fast.
Proof sketch or proof idea
Theorem 1.2.9
(Closure of regular languages)
If are regular, then , and are regular.
Proof
(Complement, product and union)
For the complement, take a DFA with total and swap accepting and non-accepting states: each word determines one run, so it ends in iff it does not end in . For intersection of and , run both machines in parallel on with accepting set ; induction on the word shows that the pair-run is the pair of runs. Union uses accepting pairs with at least one accepting coordinate, or De Morgan.
Theorem 1.2.10
(Pumping lemma for regular languages)
Let be regular. Then there is such that every with can be written with , , and for all .
Proof
(Pigeonhole on the run)
Take a DFA with states for and with . The first states of its run, , cannot be pairwise distinct, so for some . Let be the first symbols, the next symbols and the rest. Then , and reading from returns to , so reading for any also ends at . Therefore the end state for is that of or , which accepts.
Theorem 1.2.11
(Distinguishability lower bound)
If are pairwise distinguishable by , then every DFA with language has at least states.
Proof
(Equal states force equal verdicts)
Let be a DFA for . If for , then for every the words and end in the same state and are both accepted or both rejected, contradicting distinguishability. So the states are distinct.
Counterexample mode
The pumping conditions are necessary, not sufficient
Claim (false): if a language satisfies the conclusion of the pumping lemma, it is regular. Let . Take . A word of of length at least begins with , or ; let be that first letter and . If it begins with or , then becomes or and stays in the second part for every . If it is , pumping gives , which is in the first part for , and for gives , in the second part. So the conclusion holds with . Yet is not regular: the words () are pairwise distinguishable, because while when . By the distinguishability bound no finite DFA exists. Repair: the pumping lemma proves non-regularity only when it fails; use distinguishability for a two-sided test.
Worked examples
Worked example 1.2.12
(Subset construction for 'second-to-last symbol is 1')
Let have states , start , accepting , edges , and . From : on stay at , on go to . From : on to , on to . From : on to , on to . From : on to , on to . Four of the eight subsets are reachable, and the two containing accept. A word is accepted iff its second-to-last symbol is , since is entered exactly on a and is reached one symbol later.
Worked example 1.2.13
(Elimination for an even number of a's)
Over let state (start, accepting) mean an even number of 's so far and state an odd number, with swapping states and looping. Then , , , . One computes , , , , so , where means equal languages. This describes the language, and it equals , the expression obtained by removing state and rewriting the loop at . Equality of the two forms is verified by the common automaton, not by symbol manipulation.
Worked example 1.2.14
(Primes are not regular)
Let and suppose a pumping length exists. Choose a prime and put . Then with . Pump with : the new length is , a product of two integers at least , hence composite, so . This contradicts the lemma. The choice of depends on , which is legitimate because the lemma is quantified over all .
Worked example 1.2.15
(Infinitely many distinguishable words for )
For the words are pairwise distinguishable: with we have , while for . So for every any DFA for needs at least states, impossible for a finite machine, hence is not regular.
Counterexample mode
One failed split proves too little
For , use the valid pumping length : every word of length at least four can pump its first symbol. The word also has the legal split , , . Pumping twice produces , outside . Yet is regular: the lemma only requires a suitable split, not that this chosen split succeeds. For example, using in the initial zero block gives a valid loop for that word when the length condition is met.
Worked example 1.2.16
(Unary squares are not regular)
Let . Suppose has pumping length and choose . This word has length at least . For any legal split, with . Pump once more, with : the new length is .
Because ,
No integer square lies strictly between consecutive squares, so . This contradicts the lemma for every legal split. The gap argument works even though the decomposition is unknown.
Common mistakes
Common mistake
(Complementing an NFA by swapping marks)
Swapping accepting states of an NFA does not complement its language; it works only for complete DFAs, because an NFA may accept a word along one path and reject it along another.
Common mistake
(The empty language is not the empty word)
Treating as gives wrong results in star: but concatenated with anything is empty.
Common mistake
(You do not choose the pumping decomposition)
In pumping-lemma arguments, the lemma gives you and the decomposition; you do not choose the decomposition. A valid proof must handle every with and . Choosing in terms of , and then choosing , are your two free moves. Finally, the lemma cannot show that a language is regular, as the counterexample above demonstrates.
Another error is treating as the size of the DFA produced in practice. It is an upper bound for all reachable subsets, and exponential growth cannot be avoided in general: the exercise on -th symbols from the end gives an NFA with states for which every DFA needs at least states.
Summary
DFAs, -NFAs and regular expressions define the same class of languages: subsets turn nondeterminism into determinism, Thompson's construction turns expressions into automata, and the elimination recurrence turns automata into expressions. The class is closed under complement, intersection and union. Pumping gives a necessary property of regular languages, and distinguishable words give a quantitative lower bound on states. Minimization algorithms and the full characterization by equivalence classes are not covered here.
Exercises
Quick check
(Prove that is not regular, using the pumping lemma.)
Pick a word whose first symbols force the pumped part.
Solution · Answer
Let be the pumping length and . Any decomposition has , so with . Then has more 's than 's and is not in the language, a contradiction.
Quick check
(Give an NFA such that the NFA obtained by exchanging accepting and non-accepting states does not accept the complement of .)
Try an NFA over a unary alphabet with two states.
Solution · Answer
Take states , start , accepting , and edges and over the alphabet . Then , with complement . After exchanging, the accepting set is : the word reaches and is accepted, though . So the new NFA accepts all of , not .
Quick check
(For let be the set of words over of length at least whose -th symbol from the end is . Prove that every DFA for has at least states.)
Compare two words of length at their first difference.
Solution · Answer
Take the words of length . If differ first at position (counted from the left), append . Then position of and of is the -th symbol from the end of and (length ), and exactly one of them is . So are distinguishable, and the bound follows from the distinguishability bound.
Quick check
(Prove that the reversal of a regular language is regular, using an NFA.)
Reverse every edge of a DFA.
Solution · Answer
Let be a DFA for , viewed as an NFA with one start state and accepting set . Reverse every edge, make the old start state the only accepting state, and add a new start state with -edges to every member of . A path labeled from to some in corresponds exactly to a path labeled from to in the new machine. So the new -NFA accepts iff , and by the subset construction is regular. If , the new machine has no accepting path, and indeed .