MIT 18.404 — Lecture 2

Nondeterminism, Closure Properties, Regular Expressions

§ Nondeterministic Finite Automata

We first introduce a new variant of finite automata: the nondeterministic finite automata (or NFA).

In spirit, it's a finite automaton that allows processes to fork; if any process ends at an accept state, the automaton accepts.

Definition. A nondeterministic finite automaton is a finite automaton with the following alterations:

A state can have multiple outward edges with the same label.
An outward edge can have the empty string $\epsilon$ as a label. (Traversing such an edge is free.)

Formally, the distinction is simply that the transition function is now $\delta \colon Q \times \Sigma_{\epsilon} \to \mathcal{P}(Q)$ (where $\Sigma_{\epsilon} := \Sigma \cup \{\epsilon\}$ ).

Remark. There's an important note about both NFAs and DFAs that should be explained explicitly now.

Sometimes, you might read in a character $\str{c}$ while at a state with no outgoing edge with label $\str{c}$ . In such a case, you go to a dead state, meaning the string is automatically rejected.

This is true even if the state you are at is the accept state. It is because of this that $\str{aaaa}$ is a regular language, for example.

Example. In the example above:

If $M$ reads in $\str{aba}$ , then the end state could be any of $\{q_1, q_2, q_4, \textsc{Dead}\}$ . Since $q_4$ is an accept state, $M$ accepts $\str{aba}$ .
If $M$ reads in $\str{bbbbbaaaaaaa}$ , then the end state could be any of $\{q_1, q_2, \textsc{Dead}\}$ . So $M$ rejects $\str{bbbbbaaaaaaa}$ .
If $M$ reads in $\str{aaabbb}$ , then the end state could be any of $\{q_1, \textsc{Dead}\}$ . So $M$ rejects $\str{aaabbb}$ .

It turns out, very importantly, that NFAs and DFAs are just different expressions of the same thing.

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

Proof: If $A$ is recognized by some DFA $M$ , then $A$ is recognized by the same FA $M$ if interpreted as an NFA.

Meanwhile, if $A$ is recognized by some NFA $N$ , then we can design a DFA $M$ that recognizes $A$ by taking $M$ to hold one state for each subset of the set of states of $N$ . Details omitted; it's not very nontrivial. $\blacksquare$

So although it feels that nondeterminism allows for more generality than determinism… it actually changes nothing! The upshot, of course, is that in a lot of contexts, NFAs are much easier to construct than DFAs.

§ Regular Expressions are Regular Languages

To demonstrate the strength of NFAs, we'll now use them to prove the following theorem.

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

It suffices to prove the closure of regular languages under union, concatenation, and star. NFAs do this pretty easily.

(Union Proof)

(Concatenation Proof)

(Star Proof)

And that's all for today.