Nondeterministic Finite-State Automata

In order to prove Kleene’s theorem, we need to introduce yet another model of computation for regular languages to act as an intermediary between DFAs and regular expressions. This model is strictly more expressive than DFAs, making it possible to prove regularity of a language more easily than designing a DFA or a regular expression. The expressivity will also serve us well next week when we discuss taking regular languages and applying transformations to create new provably regular languages.

The idea behind the new model is to add the power of choice to DFAs. We’ll still have a finite set of states and read symbols from a string from beginning-to-end, but when reading a symbol, we get to nondeterministically choose which state to go to next. We get to guess, which of several possible transitions might lead us to an accept state. If any sequence of choices consistent with the input string leads to an accept state, then we accept the string. The members of this model are called nondeterministic finite-state automata (NFAs).

For example, the transition graph below represents an NFA that accepts all strings containing either 00 or 11 (inclusive) as a substring. NFA transition graph for binary strings containing 00 or 11

You have to read in a substring 00 to go from $s$ to $c$ through $a$ . You have to read in a substring 11 to go from $s$ to $c$ through $b$ . But you have the option of staying parked on $s$ until one of those two substrings appear, so the NFA accepts the correct language. For example, the string 0101001 could go through state transitions $s \xrightarrow{0} s \xrightarrow{1} s \xrightarrow{0} s \xrightarrow{1} s \xrightarrow{0} a \xrightarrow{0} c \xrightarrow{1}$ , so it would be accepted.

Formal definition

Formally, a nondeterministic finite-state automaton (NFA) $M = (\Sigma, Q, \delta, s, A)$ has five components:

An arbitrary finite input alphabet $\Sigma$
An arbitrary finite set of states $Q$
An arbitrary transition function that takes a state and symbol and go to a subset of states $\delta: Q \times \Sigma \to 2^Q$ . Here, $2^Q$ is mnemonic notation for the powerset of $Q$ , the set of all subsets of $Q$ . You may have seen $\mathcal{P}(Q)$ used instead. This function may even evaluate to $\varnothing$ .
A start state $s \in Q$
A subset of accepting states $A \subseteq Q$

In the formal definition, NFAs read in symbols one at a time from a string $w \in \Sigma^*$ , but instead of maintaining a single current state, they maintain a whole set of current states initially starting with $\{s\}$ . The subset being maintained is the entire subset of states that could be reached via nondeterminsitic choices consistent with the symbols being read. When the NFA reads a symbol $a$ , it applies the transition function to every member of the subset of current states, and it goes the union of all the results. In particular, if the set of current states ever goes empty, then it stays empty forever. After reading all of $w$ , the NFA accepts $w$ if any of the current states are accepting. It rejects $w$ otherwise.

Like with DFAs, we can define an extended transition function $\delta^* : Q \times \Sigma^* \to 2^Q$ which takes a single state and a string and goes to a set of states as follows: $\delta^*(q, w) := \begin{cases} \{q\} &\text{if $w = \varepsilon$}\\ \bigcup_{r \in \delta(q, a)} \delta^*(r, x) &\text{if $w = ax$}. \end{cases}$ In other words, we ask, “Where would all the states in $\delta(q, a)$ ultimately take us if we kept reading the symbols from $x$ ?” The NFA accepts $w$ if and only if $\delta^*(s, w) \cap A \neq \varnothing$ , and it rejects $w$ otherwise. Its language is the set of strings it accepts: $L(M) := \{w \mid \delta^*(s, w) \cap A \neq \varnothing\}$

Common extensions

There are two common extensions to the standard definition of NFAs that make them easier to design without actually changing the set of languages they can accept. The first is based on the observation that NFAs always maintain arbitrary subsets of states as they read in the input string. So why, then, are we restricting ourselves to start with exactly one state? For example, this (one) NFA has two start states. NFA with multiple start states transition graph for binary strings containing 00 or 11

We can interpret a run of the NFA as nondeterministically choosing one of the start states and then nondeterministically doing transitions as discussed before. Formally, an NFA with start states $S \subseteq Q$ accepts $w$ if and only if $(\bigcup_{s \in S} \delta^*(s, w)) \cap A \neq \emptyset$ .

Again, it’s no more powerful than what we’ve seen already. Given an NFA with multiple start states $S$ , we can construct one with a single start state by

adding a new state $\bar{s}$ ,
copying all outgoing transitions from $S$ to leave $\bar{s}$ instead,
declaring $\bar{s}$ to be an accepting state if and only if $S$ contains an accepting state,
and declaring $\bar{s}$ as the one start state.

Here’s what happens to the two start state NFA: NFA with multiple start states undone transition graph for binary strings containing 00 or 11

The second common extension is to allow for $\varepsilon$ -transitions that allow the machine to change state without having to read an input symbol. For example, this silly machine still accepts the same language as last time: NFA with multiple start states undone transition graph for binary strings containing 00 or 11

In the intuition of guessing a path through the NFA, you can optionally take any $\varepsilon$ -transition you’d like leaving your current state. Formally, we redefine the transition function as $\delta: Q \times (\Sigma \cup \{\varepsilon\}) \to 2^Q$ . Let $\varepsilon\text{-reach}(q)$ for a state $q \in Q$ be the set of states reachable by a sequence of $\varepsilon$ -transitions. In other words, if we consider the graph $G$ of NFA states and $\varepsilon$ -transitions between them, the $\varepsilon\text{-reach}(q)$ is exactly the set of vertices $r$ for which there is a path from $q$ to $r$ . Then, $\delta^*(p, w) := \begin{cases} \varepsilon\text{-reach}(p) &\text{if $w = \varepsilon$}\\ \bigcup_{r \in \varepsilon\text{-reach}(p)} \bigcup_{q \in \delta(r, a)} \delta^*(q, x) &\text{if $w = ax$}. \end{cases}$ In other words, grab all the states you can reach via $0$ or more $\varepsilon$ -transitions, read a symbol, and recurse.

$\varepsilon$ -transitions can be very convenient for constructing NFAs, but (again) they don’t actually makes NFAs any more powerful! Given an NFA $M = (Q, \delta, S, A)$ with $\varepsilon$ -transitions and multiple start states, we can make a new one without $\varepsilon$ -transitions.¹ In short, if $q \in \varepsilon\text{-reach}(p)$ , then we add all actual symbol transitions out of $q$ to leave $p$ instead. Additionally, we update the accept states to include the $\varepsilon$ -reaches of all the original accept states.

TODO: Make a figure.

More formally, we make a new NFA $M' = (Q, \delta', S, A')$ from $M$ where

$\delta'(p, a) = \bigcup_{q \in \varepsilon\text{-reach}(p)} \delta(q, a)$ and
$A' = \bigcup_{q \in A} \varepsilon\text{-reach}(q)$ .

Note that I’m using a somewhat different construction than shown in Erickson’s Models 4 to (in my opinion) better match the above definition of $\delta^*$ .

TODO: “Prove” Kleene’s theorem.