MIT 18.404 — Lecture 3

Regular Expressions, The Pumping Lemma

§ Generalized NFAs

Recall that we proved in Lecture 2 the following theorem by introducing a new kind of FA (the NFA).

Theorem. (Regularness) Every regular expression is a regular language.

In this lecture, we'll introduce another kind of FA—the generalized NFA (GNFA)—to prove the reverse direction.

Theorem. (Regularness) Every regular language is a regular expression.

Definition. A generalized NFA is an NFA in which edges may be labeled with any regular expression (not just atoms!). We say a GNFA is good if it satisfies the following properties:

There is a single accept state distinct from the start state.
There exists a transition between every pair of states and a self-loop at every state (possibly with label $\emptyset$ ) …
- … except the start state must have indegree zero …
- … and the accept state must have outdegree zero.

Evidently, every GNFA can be easily translated into a good GNFA by adding $\emptyset$ edges and some additional states.

Expectedly, good GNFAs are equally as representative of regular languages as ordinary NFAs (or DFAs) are.

Theorem. (GNFA Implies NFA) A language $A$ is recognized by some NFA if and only if $A$ is recognized by some GNFA.

Proof: The NFA $\implies$ GNFA direction is trivial, so we only show the GNFA $\implies$ NFA direction.

Simply apply the fact from Lecture 2 that every regular expression is the language of some NFA. That is, for each edge with regular expression $r$ , replace that edge with the NFA whose language is $r$ , linking into and out of the NFA using $\epsilon$ -edges.

If this new NFA accepts a string $s$ , then the original GNFA must also accept $s$ ; to see why, consider breaking up the computation path of $s$ into sub-paths $p \to q$ where $p$ and $q$ are states of the original GNFA, and so… $\blacksquare$

§ Regular Languages are Regular Expressions

We now prove the following theorem.

Theorem. (GNFA Regularness) Every good GNFA regular language is a regular expression.

Proof: Proof by induction on the number of states. The base case is trivial.

For the inductive step, remove a state $X$ from the GNFA $G$ that is not the start or accept state.

Furthermore, for every ordered pair of states $(p, q) \in (Q \setminus \{X\})^2$ , update the label of the edge $p \to q$ as shown above. This leaves the language of $G$ unchanged, so we can induct down successfully. $\blacksquare$

Remark. CYU: Where, in the proof, does the “goodness” of the GNFA get used?

And of course, by combining this theorem with the “GNFA Implies NFA” theorem preceding it, we get:

Theorem. (DFA Regularness) Every (DFA) regular language is a regular expression.

§ Proving Nonregularity

All of our work so far has gone toward proving the regularity of languages. What about nonregularity?

Example. Consider the following languages with alphabet $\Sigma = \{\str{0}, \str{1}\}$ .

B := \{w \mid w \text{ has as many } \str{0}\text{s} \text{ as } \str{1}\text{s}\} ~~~ \parallel ~~~ C := \{w \mid w \text{ has as many } \str{01}\text{s} \text{ as } \str{10}\text{s}\}

As we'll see, $B$ is nonregular. But $C$ is regular—consider a five-state FA that tracks $(\textsc{First Symbol}, \textsc{Last Symbol})$ .

Theorem. (Pumping Lemma) For every regular language $A$ , there must be some pumping length $p$ such that:

For all $s \in A$ with $|s| \geq p$ , we may write $s = xyz$ with $y \neq \epsilon$ such that $|xy| \leq p$ and $xy^iz \in A$ for all $i \in \mathbb{N}$ .

Proof: The pumping length of $A = L(M)$ is the number of states in the FA $M$ .

Consider some string $s \in A$ with $|s| \geq p$ . Suppose it begins at $S$ and ends at $T$ through some path $\mathcal{P}$ . Since $|s| \geq p$ , the path $\mathcal{P}$ must land on some state twice. Say this happens for the first time at state $L$ .

Then taking $(x, y, z) := (S \to L, L \to L, L \to T)$ just works. $\blacksquare$

Remark. All finite languages are regular. And this is trivially consistent with the pumping lemma—why?

Problem. Prove that the language $D := \{\str{0}^k \str{1}^k \mid k \geq 0\}$ is not regular.

Solution: Argue by contradiction. If the pumping length were $p$ , then $s = \str{0}^p\str{1}^p \in D$ would contradict the pumping lemma. $\blacksquare$

Problem. Prove that the language $B := \{w \mid w \text{ has as many } \str{0}\text{s} \text{ as } \str{1}\text{s}\}$ is not regular.

Solution: The point is that if $B$ is regular, then so is $D = B \cap \str{0}^*\str{1}^*$ (by closure). Contradiction by the previous problem. $\blacksquare$

Unfortunately, there exist nonregular languages that satisfy the pumping lemma; take $\str{1}\str{1}^*D \cup \str{0}^*\str{1}^*$ with pumping length $1$ , say.