Regular and context-free languages, pumping lemma

Language-class hierarchy

Definition. Every regular language is context-free because a CFG can simulate a finite automaton. The inclusion is strict: some CFLs, such as {aⁿbⁿ:n≥0}, are not regular. Some languages are not context-free, such as {aⁿbⁿcⁿ:n≥0}.

Class	Typical machine	Example	Strict inclusion
Regular	DFA/NFA/regular expression	strings ending in 01	contained in CFL
Context-free	NPDA/CFG	{aⁿbⁿ}	contained in decidable languages
Decidable	halting TM decider	{⟨M,w⟩: M accepts w within 100 steps}	broader than CFL
Recognizable	TM recognizer	halting problem language	includes undecidable languages

Example. {aⁿbⁿ} is generated by S→aSb|ε, so it is context-free; its unequal-count boundary makes it nonregular.

Exam point. A language being nonregular does not imply it is non-context-free.

Solved examples

Example 1 — classify a suffix condition. Classify L={w∈{0,1}*: w ends in 01}.

1. A finite automaton needs only remember the longest suffix that is a prefix of 01.
2. Use states for no useful suffix, suffix 0, and suffix 01.
3. This DFA has finitely many states, so L is regular.
4. Classification: regular, therefore also context-free.

Example 2 — equal blocks. Classify {aⁿbⁿ:n≥0}.

1. CFG S→aSb|ε generates exactly matching blocks.
2. A PDA pushes on each a and pops on each b.
3. Pumping lemma for regular languages proves it is not regular.
4. Classification: context-free but not regular.

Example 3 — three matched blocks. Classify {aⁿbⁿcⁿ:n≥0}.

1. A single stack can compare one block count with another but cannot retain both independent equalities in the needed order.
2. The CFL pumping lemma gives a formal non-CFL proof: a short pump region cannot affect all three blocks equally.
3. Classification: not context-free.

Myhill-Nerode equivalence and regularity

Definition. For language L, strings x and y are equivalent if for every suffix z, xz∈L iff yz∈L. L is regular exactly when this equivalence has finitely many classes. Pairwise distinguishable prefixes provide a lower bound on DFA states.

Example. For strings whose number of 1s is divisible by 3, prefixes with counts 0,1,2 modulo 3 are pairwise distinguishable.

Exam point. Pumping lemma can prove nonregularity; Myhill-Nerode can also give exact state lower bounds and prove regularity when classes are finite.

Solved examples

Example 1 — at least n zeros. Let L={0^k:k≥3} over unary alphabet. Determine an equivalence partition.

1. Prefixes of lengths 0,1,2 are distinct because suffix 0^(3-i) makes one reach length 3 sooner than another.
2. All prefixes of length at least 3 are equivalent: every continuation remains in L.
3. There are four classes: lengths 0,1,2, and ≥3.
4. A minimal DFA has four states.

Example 2 — prove nonregular by infinitely many classes. Let L={0ⁿ1ⁿ:n≥0}. Consider prefixes 0^i for i≥0.

1. Take i<j and choose suffix 1^i.
2. 0^i1^i∈L.
3. 0^j1^i∉L because counts differ.
4. Every pair is distinguishable, producing infinitely many classes. L is nonregular.

Regular pumping lemma strategy

Definition. The pumping lemma is a consequence of finite-state repetition: while a DFA reads a sufficiently long string, some state repeats within the first p+1 visited states. The repeated segment can be removed or repeated while preserving acceptance.

Example. In a DFA with p states, any accepted string of length at least p has a repeated state among the first p+1 states.

Exam point. Quantifier order matters: choose s after p is given, then handle every legal decomposition.

Solved examples

Example 1 — language with prime length. Show {a^m : m is prime} is not regular.

1. Assume regular with pumping length p; choose prime q≥p and s=a^q.
2. Any legal decomposition has y=a^k with 1≤k≤p.
3. Pump i=q+1, obtaining length q+qk=q(1+k).
4. Since 1+k>1, this length is composite.
5. Contradiction; the prime-length unary language is nonregular.

Example 2 — finite languages are regular. Explain why any finite language L is regular.

1. For each string w∈L, a finite chain of states can check that exact sequence.
2. Branch these chains from a common start using an NFA.
3. Make each chain endpoint accepting and reject all unmatched continuations.
4. The finite NFA recognizes L, so L is regular.

CFL pumping lemma

Definition. For every CFL L there is a pumping length p such that any s∈L with |s|≥p can be written s=uvxyz, where |vxy|≤p, |vy|≥1, and uv^i x y^i z∈L for all i≥0. The two pumped regions may occur in nearby positions.

Example. The lemma can prove {aⁿbⁿcⁿ} is not context-free because a pump window of bounded length cannot change all three equal block counts together.

Exam point. The bound is on vxy, not on the entire prefix uv; both v and y are pumped simultaneously.

Solved examples

Example 1 — non-CFL proof for three blocks. Let L={aⁿbⁿcⁿ:n≥0}; assume it is CFL and choose s=a^p b^p c^p.

1. For any split satisfying |vxy|≤p, the substring vxy can lie in one block or cross only one adjacent boundary; it cannot contain both an a and a c because the full b block has length p.
2. Pumping i=0 removes symbols from v and y, which are confined to one block or two adjacent blocks.
3. At least one of the three counts stays p while at least one other changes; or the block order breaks if a boundary is altered.
4. The result cannot have equal a,b,c counts in order.
5. Contradiction; L is not context-free.

Example 2 — why one pumped part can be empty. In a CFL pumping decomposition, can v=ε?

1. The conditions require |vy|≥1, not that both v and y are nonempty.
2. One of v or y may be ε while the other is nonempty.
3. A proof must rely on the total pumped material being nonempty.

Classifying a language: practical decision path

Definition. Classification should proceed from simplest witnesses and machine models: seek a regular expression/DFA; if counting or nesting needs one stack, seek a CFG/PDA; use pumping or closure arguments to prove a claimed class impossible. A construction proves membership; a lower-bound theorem proves nonmembership.

Question	Evidence for yes	Evidence for no
Regular?	regex, DFA, closure construction, finite Nerode classes	regular pumping lemma, infinite Nerode classes
Context-free?	CFG or PDA construction	CFL pumping lemma, closure reduction
Neither?	first show non-CFL	nonregular alone is insufficient

Example. {ww:w∈{0,1}*} is not regular and is not context-free; the latter needs a CFL-level argument, not merely the regular pumping lemma.

Exam point. Never conclude “not CFL” from “not regular”; the classes are strictly nested.

Solved examples

Example 1 — regular by expression. Classify {w∈{a,b}*: w has no b}.

1. The language is a*.
2. A one-state accepting DFA with a b-transition to a rejecting sink also recognizes it.
3. Regular and therefore context-free.

Example 2 — CFL but not regular. Classify {a^i b^j : i=j or j=0}.

1. It is {a^n b^n:n≥0} ∪ a*.
2. The first language is context-free and a* is regular; CFLs are closed under union with regular languages.
3. It is nonregular: for prefixes a^i with i,j≥1 and i<j, distinguish them by suffix b^i (the shorter prefix yields equal counts; the longer yields unequal positive counts and is not in the language).
4. Classification: CFL but not regular.

Example 3 — order constraint only. Classify {a^i b^j c^k:i,j,k≥0}.

1. A regular expression is a*b*c*.
2. The expression forces all a's before b's before c's and permits each count to be zero.
3. Regular, hence context-free.

Example 4 — complement trap. If L is nonregular, must its complement be nonregular?

1. If complement(L) were regular, closure of regular languages under complement would make L regular.
2. This contradicts the assumption.
3. Yes: the complement of a nonregular language cannot be regular.

Closure properties: regular versus context-free

Definition. Closure lets us transfer language membership through operations. Regular languages have stronger Boolean closure than CFLs; CFLs are closed under union, concatenation, star, reversal, and homomorphisms, but not under intersection or complement in general.