9  Finite Automata

In this chapter we investigate our first couple of computational models: \varepsilon-NFAs and DFAs, and we show their equivalence (Theorem 9.2).

WarningUpdates post-class

9.1 Nondeterministic Finite Automata

Informally a Nondeterministic Finite Automaton (\varepsilon-NFA) A is a directed graph (with loops) where the edges have labels which are either \varepsilon or some symbol from a given alphabet \Sigma, and there are two sets of distinguished vertices (the initial and final, or accepting states). The set of initial states must be non-empty, but the set of final states may be empty. The graph can have multiple edges between two vertices, and it can have loops (edges from a vertex to itself).

The vertices of the graph are usually called states, the edges transitions.

Initial states are represented with an incoming arrow1 and final states are represented with a double circle.

Example 9.1 Figure 9.1 represents an \varepsilon-NFA with two states (q_0, an initial state and q a final state) and no transitions.

Figure 9.1

Transitions are represented with arrows, and the label of the transition is written next to the arrow.

Example 9.2 In Figure 9.2, there is a transition from q_1 to itself with label \textcolor{darkred}{\mathtt{b}}, a transition from q_1 to q_3 with label \varepsilon and two transitions from q_1 to q_2 with labels \textcolor{darkred}{\mathtt{a}} and \textcolor{darkred}{\mathtt{c}}. A transition with label \varepsilon is called an \varepsilon-transition. Transitions given by parallel edges are usually written as a single edge with multiple labels, for example the two edges from q_1 to q_2 in Figure 9.2 can be represented as a single edge with label \textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{c}} (as in Figure 9.3).

Figure 9.2
Figure 9.3

Notice that Figure 9.2 and Figure 9.3 are not \varepsilon-NFAs since there are no marked initial states.

Formally, an \varepsilon-NFA is given by a tuple (Q,\Sigma,I,F,\delta) where

  • Q is a finite set of states (the set of vertices in the directed graph);
  • \Sigma is the alphabet of possible simbols occurring as labels of the edges;
  • I (non-empty) and F are subsets of Q, resp. the initial and final states;2
  • \delta \subseteq Q\times (\Sigma\cup\{\varepsilon\})\times Q is a relation (called transition relation) describing the labels of the edges of the graph: the edge (q,q') has label \textcolor{darkred}{\mathtt{s}} if and only if (q,\textcolor{darkred}{\mathtt{s}},q')\in \delta, and similarly for \varepsilon.
NoteOn notation

In some texts, an \varepsilon-NFA is defined using a transition function \delta':Q\times (\Sigma\cup \{\varepsilon\})\to \mathscr{P}(Q) instead of a transition relation \delta \subseteq Q\times (\Sigma\cup\{\varepsilon\})\times Q. This is just a matter of notation, it is immediate to translate from one notation to the other: given \delta' we have that \delta=\{(q,\textcolor{darkred}{\mathtt{s}},q')\in Q\times (\Sigma\cup\{\varepsilon\})\times Q :q'\in \delta'(q,\textcolor{darkred}{\mathtt{s}}) \} and, viceversa, given \delta, we have that \delta'(q,\textcolor{darkred}{\mathtt{s}})=\{q'\in Q:(q,\textcolor{darkred}{\mathtt{s}},q')\in \delta \}.

We associate a language to an \varepsilon-NFA as follows.

Definition 9.1 The language accepted by an \varepsilon-NFA A is \mathscr{L}(A). A word w\in \Sigma^* is in \mathscr{L}(A) if and only if there exist a sequence of states q_1,\dots,q_m in A and s_1,\dots,s_{m-1}\in \Sigma\cup\{\varepsilon\} s.t.

  • q_1 is an initial state of A;
  • q_m is a final state of A;
  • for each i\in \{1,\dots, m-1\}, (q_i,s_i,q_{i+1}) is in the transition relation of A, that is (q_i,q_{i+1}) is an edge in A with label s_i; and
  • the concatenation s_1\cdots s_{m-1} gives the word w.

The path q_1,\dots,q_m is an accepting path for w in A.

Example 9.3 Consider the following \varepsilon-NFA A over the alphabet \Sigma=\{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}},\textcolor{darkred}{\mathtt{c}}\}:

Figure 9.4

What is the language \mathscr{L}(A) accepted by the \varepsilon-NFA A in Figure 9.4?

The language accepted by the \varepsilon-NFA A in Figure 9.4 is the empty word \varepsilon together with the set of words in \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}},\textcolor{darkred}{\mathtt{c}}\}^* that contain at least one occurrence of the word \textcolor{darkred}{\mathtt{ab}}, that is

\mathscr{L}(A)=\{\varepsilon\}\cup\{w\in \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}},\textcolor{darkred}{\mathtt{c}}\}^* :|w|_{\textcolor{darkred}{\mathtt{ab}}}\geq 1 \}\ .

Exercise 9.1 (Simple (almost trivial) \varepsilon-NFAs) Contruct \varepsilon-NFAs for the following languages:

  1. \emptyset.
  2. \{\varepsilon\}.
  3. \{\textcolor{darkred}{\mathtt{s}}\} where \textcolor{darkred}{\mathtt{s}}\in \Sigma.

Exercise 9.2 Construct \varepsilon-NFAs accepting the following languages:

  1. The language consisting of a single word: \textcolor{darkred}{\mathtt{101}};
  2. The language of all words in \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}^* starting with \textcolor{darkred}{\mathtt{101}};
  3. The language of all words in \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}^* ending with \textcolor{darkred}{\mathtt{101}};
  4. The language of all words in \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}^* containing \textcolor{darkred}{\mathtt{101}} as a subword.

Exercise 9.3 Given an \varepsilon-NFA A, show that there exists an \varepsilon-NFA B with exactly one initial and one final state s.t. \mathscr{L}(A)=\mathscr{L}(B).

Exercise 9.4 (Operations on \varepsilon-NFAs) Given \varepsilon-NFAs A and B,

  1. construct an \varepsilon-NFA accepting \mathscr{L}(A)\cup\mathscr{L}(B).
  2. construct an \varepsilon-NFA accepting \mathscr{L}(A)\cdot\mathscr{L}(B).
  3. construct an \varepsilon-NFA accepting \mathscr{L}(A)^*.

9.2 Deterministic Finite Automata

The next computational model is a special case of \varepsilon-NFAs.

Definition 9.2 An \varepsilon-NFA A is deterministic, aka it is a Deterministic Finite Automaton (DFA) if

  • there is exactly one initial state,
  • there are no edges with label \varepsilon and
  • for every state there is exactly one outgoing edge with label \textcolor{darkred}{\mathtt{s}} for each \textcolor{darkred}{\mathtt{s}}\in \Sigma.

Formally, a DFA is given by a tuple (Q,\Sigma,I,F,\delta) where

  • Q is a finite set of states (the set of vertices in the directed graph);
  • \Sigma is the alphabet of possible simbols occurring as labels of the edges;
  • I and F are subsets of Q and I has size one;
  • \delta: Q\times \Sigma\to Q is a function (called transition function) describing the labels of the edges of the graph: the edge (q,q') has label \textcolor{darkred}{\mathtt{s}} if and only if q'= \delta(q,\textcolor{darkred}{\mathtt{s}}).

Example 9.4 As an example, let’s give a DFA accepting the same language as the \varepsilon-NFA A in Figure 9.4, that is all the words over \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}},\textcolor{darkred}{\mathtt{c}}\} with at least an occurrence of \textcolor{darkred}{\mathtt{ab}} or the word \varepsilon.

Figure 9.5

The state q_2 marks the fact that we have seen an \textcolor{darkred}{\mathtt{a}} and we are waiting for a \textcolor{darkred}{\mathtt{b}} to accept the word. The state q_3 marks the fact that we have seen an \textcolor{darkred}{\mathtt{ab}} and hence we can accept any continuation of the word. The state q_1 marks the fact that we have seen some symbol, but not an \textcolor{darkred}{\mathtt{a}} yet, or that we have seen an \textcolor{darkred}{\mathtt{a}} but it was not followed by a \textcolor{darkred}{\mathtt{b}}. The state q_0 is just to accept \varepsilon.

In an \varepsilon-NFA A, to check whether a given word w is in \mathscr{L}(A) or not we might need to check exponentially many paths, but given a path that supposedly shows that w\in \mathscr{L}(A) it is easy to check it is indeed a correct witness.

The “N” in NFA and in \mathbf{NP} refer to the same phenomenon, the nondeterminism.

For a DFA B checking whether a given word w is in \mathscr{L}(B) is trivial, there is always exactly one path starting from the initial state whose labels once concatenated give the word w. If this path ends in an final state, then w\in \mathscr{L}(L), otherwise w\notin\mathscr{L}(L).

Exercise 9.5 (Operations on DFAs) Given a DFA A and a homomorphism \sigma,

  1. construct a DFA accepting \overline{\mathscr{L}(A)}.
  2. construct an \varepsilon-NFA accepting \mathscr{L}(A)^R.
  3. (🔥) construct a \varepsilon-NFA accepting \sigma(\mathscr{L}(A)).
  4. (🔥) construct an \varepsilon-NFA accepting \sigma^{-1}(\mathscr{L}(A)).

9.3 Equivalence

In this section we show that we can simplify \varepsilon-NFAs, to get equivalent NFAs (i.e. \varepsilon-NFA without \varepsilon-transitions), and DFAs. The price to pay in the first case is to have more transitions, and in the second case to have a potentially exponentially larger number of states.

Theorem 9.1 For every \varepsilon-NFA A, there exists an \varepsilon-NFA B without \varepsilon transitions s.t. \mathscr{L}(A)=\mathscr{L}(B).

Let A=(Q,\Sigma,I,F,\delta). For two states q,q'\in Q we write q\stackrel{\varepsilon^*}{\to}q' if q' is reachable from q following 0 or more \varepsilon-transitions and we write q\stackrel{\textcolor{darkred}{\mathtt{s}}}{\to}q' if (q,\textcolor{darkred}{\mathtt{s}},q')\in \delta, that is if q' is reachable in one step from q following a transition with label \textcolor{darkred}{\mathtt{s}}\in \Sigma.

Let’s now describe the \varepsilon-NFA B=(Q,\Sigma,I,F',\delta') without \varepsilon transitions s.t. \mathscr{L}(A)=\mathscr{L}(B):

  • F'=\{q\in Q :\exists q'\in F,\ q \stackrel{\epsilon^*}{\to}q'\}, that is, the final initial states are the ones that can reach by \varepsilon-transition some final state of A;
  • for each q,q'\in Q and \textcolor{darkred}{\mathtt{s}}\in \Sigma we have (q,\textcolor{darkred}{\mathtt{s}},q')\in \delta' if and only if \exists q^{\prime\prime}\in Q s.t. q\stackrel{\epsilon^*}{\to} q^{\prime\prime} \stackrel{\textcolor{darkred}{\mathtt{s}}}{\to} q', that is q' is now reachable in one step reading the symbol \textcolor{darkred}{\mathtt{s}} from q if in A it was possible to each q' from q first doing 0 or more \varepsilon-transitions and then reading \textcolor{darkred}{\mathtt{s}}.

By construction B does not have \varepsilon-transitions. Let’s check now that \mathscr{L}(A)=\mathscr{L}(B).

\mathscr{L}(A)\supseteq\mathscr{L}(B)
Let w\in \mathscr{L}(B) and let |w|=n. By construction, it means that there is a sequence of vertices q_0,q_1,\dots,q_n in B such that q_0\stackrel{w[1]}{\to} q_1 \stackrel{w[2]}{\to} q_2 \to \cdots \to q_{n-1}\stackrel{w[n]}{\to} q_n with q_0\in I and q_n\in F'. By definition of \delta' this means there are vertices q_0',\dots,q_n' in A s.t. q_0 \stackrel{\varepsilon^*}{\to}q_0'\stackrel{w[1]}{\to} q_1 \stackrel{\varepsilon^*}{\to} q_1' \stackrel{w[2]}{\to} q_2 \to \cdots \to q_{n-1}\stackrel{\varepsilon^*}{\to} q_{n-1}'\stackrel{w[n]}{\to} q_n\stackrel{\varepsilon^*}{\to}q_n' \tag{9.1} where q_{n'}\in F. (Notice that the vertices q_0,\dots,q_n can be seen also as vertices of A). The sequence of vertices in Equation 9.1 gives an accepting path for w in A, hence w\in \mathscr{L}(A).

\mathscr{L}(A)\subseteq\mathscr{L}(B)
The argument to prove this containment is similar to the previous one and left as an exercise (Exercise 9.6).

Example 9.5 The construction in the proof of Theorem 9.1 when applied to the \varepsilon-NFA in Figure 9.4 gives the following NFA:

Figure 9.6

Exercise 9.6 Complete the proof of Theorem 9.1 proving that \mathscr{L}(A)\subseteq\mathscr{L}(B).

Exercise 9.7 The proof of Theorem 9.1 is algorithmic and gives a way to construct B.

  1. Describe an algorithm that on input q\in Q finds all the q' s.t. q\stackrel{\varepsilon^*}{\to} q'.
  2. Following the argument in the proof of Theorem 9.1 give an explicit algorithm to construct B. What is the cost of this algorithm w.r.t. the size of the input \varepsilon-NFA A?

The set of all q' s.t. q\stackrel{\varepsilon^*}{\to} q' is called \varepsilon-closure of q.

Exercise 9.8 The construction used to prove Theorem 9.1 is called “backward closure” since we try to apply all \varepsilon-transitions before normal transitions. What would change in the argument if we wanted to use a “forward closure”, that is try to apply all \varepsilon-transitions after normal transitions?

Theorem 9.2 For every \varepsilon-NFA A, there exists a DFA B s.t. \mathscr{L}(A)=\mathscr{L}(B).

By Theorem 9.1, there is an NFA C without \varepsilon-transitions s.t. \mathscr{L}(A)=\mathscr{L}(C). Let C=(Q,\Sigma,I,F,\delta). The idea behind the construction of the DFA B is to keep track in what states of Q we can be after reading 0, 1, 2, etc symbols. These are the states of B.

At the beginning, i.e. after reading 0 symbols we can be in any of the initial states I of Q. For each S\subseteq Q and symbol \textcolor{darkred}{\mathtt{s}}\in \Sigma, what are the sets we can go from some some state in S following a transition with label \textcolor{darkred}{\mathtt{s}} maintaining the invariant that if we could have been in any of the states in S, following the transition with label \textcolor{darkred}{\mathtt{s}} we can end-up in any of the states of the new set? We can only go to the set of states

\{q\in Q :\exists x\in S, (x,\textcolor{darkred}{\mathtt{s}},q)\in \delta\}\ .

What are then the final states? All the subsets that have non-empty intersection with F.

Formally, the DFA B has set of states Q'=\mathscr{P}(Q),3 initial state I and final states \{S :S\cap F\neq \emptyset\}. The transition function \delta':Q'\times \Sigma \to Q' is defined as follows: for every S\in Q' and \textcolor{darkred}{\mathtt{s}}\in \Sigma, \delta'(S,\textcolor{darkred}{\mathtt{s}})=\{q\in Q :\exists x\in S, (x,\textcolor{darkred}{\mathtt{s}},q)\in \delta\}\ .

By construction B is a DFA and we need to show that \mathscr{L}(C)=\mathscr{L}(B). To do so we show the two containments.

\mathscr{L}(C)\subseteq \mathscr{L}(B)
w\in \mathscr{L}(C) by definition means there exists a sequence of states q_1,\dots,q_{|w|} in Q such that q_1\in I, q_{|w|}\in F and the label of the edge (q_i,q_{i+1}) is w[i], that is (q_i,w[i],q_{i+1})\in \delta. It is easy to show (by induction on i) that there exists a sequence of states S_1,\dots,S_{|w|} in B s.t. for each i, q_i\in S_i and \delta(S_i,w[i])=S_{i+1}. Since q_{|w|}\in F, then S_{|w|} is a final state of B and since S_1=I, the sequence S_1,\dots,S_{|w|} gives an accepting path for w in B, which means w\in \mathscr{L}(B).
\mathscr{L}(C)\supseteq \mathscr{L}(B)
w\in \mathscr{L}(B) means that there exists a sequence S_1,\dots,S_{|w|} of states s.t. S_1=I, S_{|w|} is a final state and for each i\leq |w|-1, S_{i+1}=\delta(S_i,w[i]). We want to find a sequence of states in C witnessing the fact that w\in \mathscr{L}(C). Construct the sequence from the end: let q_{|w|} be a state in S_{|w|}\cap F (we know it exists since S_{|w|} is a final state of B and hence S_{|w|}\cap F\neq \emptyset). Suppose now we already found the sequence q_{i+1},\dots,q_{|w|} s.t. q_{i+1}\in S_{i+1} and for each j between i+1 and |w|-1, the transition q_{j},q_{j+1} is labeled with w[j]. By construction \delta'(S_{i},w[i])=S_{i+1}, that is there exists a q_i\in S_{i} s.t. (q_i,w[i],q_{i+1})\in \delta. This is exactly what was needed for the inductive argument to continue towards the construction of q_{1},\dots,q_{|w|} with q_i\in S_1=I witnessing the fact that w\in \mathscr{L}(C).

The construction in the proof of Theorem 9.2 is called powerset construction or determinization.

Example 9.6 As an example let’s apply the powerset construction to the \varepsilon-NFA A in Figure 9.4. First we obtain an NFA eliminating all the \varepsilon-transitions from A and we obtain the NFA C in Figure 9.6. Since C has 5 states, applying the construction of Theorem 9.2 to the NFA C leads to a DFA B with 2^5=32 states. It is obvious that most of them will be redundant, for example already in C the state q_2 is useless since it has no incoming transition.

Let’s construct B step by step, i.e. only introducing the states that we can actually reach from the initial state.

The initial state of B is \{q_0,q_4\}. The part of B seen so far is:

We mark a state in yellow as a reminder that the state must be in B but we have not yet written down all possible transitions leaving it.

From \{q_0,q_4\} following an \textcolor{darkred}{\mathtt{a}} we go to \{q_0,q_1\}, while when following a \textcolor{darkred}{\mathtt{b}} or a \textcolor{darkred}{\mathtt{c}} we go to \{q_0\}. The part of B seen so far is:

If we are in \{q_0\} and we read either an \textcolor{darkred}{\mathtt{b}} or a \textcolor{darkred}{\mathtt{c}} we stay in \{q_0\}, while if we read an \textcolor{darkred}{\mathtt{a}} we go to \{q_0,q_1\}. The part of B seen so far is:

If we are in \{q_0,q_1\} when reading an \textcolor{darkred}{\mathtt{a}} we stay in \{q_0,q_1\}, when reading a \textcolor{darkred}{\mathtt{b}} we go to \{q_0,q_3\}, while when reading a \textcolor{darkred}{\mathtt{c}} we go to q_0. The part of B seen so far is:

From \{q_0,q_3\} when reading an \textcolor{darkred}{\mathtt{a}} we go to \{q_0,q_1,q_3\}, while when reading either a \textcolor{darkred}{\mathtt{b}} or a \textcolor{darkred}{\mathtt{c}} we remain in \{q_0,q_3\}. The part of B seen so far is:

From \{q_0,q_1,q_3\} when reading an \textcolor{darkred}{\mathtt{a}} we stay in \{q_0,q_1,q_3\}, while when reading either a \textcolor{darkred}{\mathtt{b}} or a \textcolor{darkred}{\mathtt{c}} we go to \{q_0,q_3\}. The part of B seen so far is:

There are no more yellow states so we wrote down all the states (out of the 32 theoretically possible ones) that are actually reachable from the initial state \{q_0,q_4\}. To conclude the construction we only need to mark the final states, that is each state corresponding to a set containing a final state of C.

The DFA B coming out of the construction in Theorem 9.2 (without writing states unreachable from the initial state) is

Figure 9.7: A DFA accepting the same language of the \varepsilon-NFA of Figure 9.4.

Exercise 9.9 (🌱) Just looking at Figure 9.7, construct a DFA with 4 states that accepts the same language. Chech that the DFA you constructed is isomorphic4 to the one in Figure 9.5.

Exercise 9.10 Based on the proof of Theorem 9.2 and Example 9.6 give an explicit algorithm that given as input an \varepsilon-NFA gives as output an equivalent DFA. What is the worst case cost of the algorithm w.r.t. the number of states of the \varepsilon-NFA gives as input?

Exercise 9.11 Given n\in \mathbb N, consider the language L_n=\{x\textcolor{darkred}{\mathtt{a}}y :x,y\in \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}}\}^* \land |y|=n\}\ , that is, L_n is the set of all words over \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}}\} with an \textcolor{darkred}{\mathtt{a}} in the n+1-th position from the end of the word.

  1. Write an \varepsilon-NFA A with n+2 states s.t. \mathscr{L}(A)=L_n.
  2. Write a DFA B with 2^{n+1} states s.t. \mathscr{L}(B)=L_n.

9.4 The cartesian product construction

There is another famous construction in DFA theory: the cartesian product construction. This procedure, given two DFAs A and B, constructs a DFA for \mathscr{L}(A)\cup \mathscr{L}(B). It is just a special case of the powerset construction (were we don’t write unnecessary states).

Example 9.7 (cartesian product construction) Given two DFAs A and B we want to construct a DFA for \mathscr{L}(A)\cup \mathscr{L}(B).

First construct an NFA for \mathscr{L}(A)\cup \mathscr{L}(B): this is trivial, take the two graphs of the DFAs and write them next to each other. This looks mostly like a DFA with the exception that there are two initial states, hence it is a NFA. If we determinize it as in the proof of Theorem 9.2 it is easy to see that the only subsets that we will ever need have size 2 and consists of a state of A and a state of B.

It is also easy to modify the construction above to give a DFA for \mathscr{L}(A)\cap \mathscr{L}(B): compared to the DFA for \mathscr{L}(A)\cup \mathscr{L}(B) the only difference are the final states. In the the DFA for \mathscr{L}(A)\cup \mathscr{L}(B) the final states are of the form \{q,q'\} where q is final in A or q' is final in B. In the DFA for \mathscr{L}(A)\cap \mathscr{L}(B) the final states are of the form \{q,q'\} where q is final in A and q' is final in B.

Exercise 9.12 Given DFAs A and B give an algorithm to compute a DFA for \mathscr{L}(A)\,\Delta\,\mathscr{L}(B) (\Delta denotes the symmetric difference of two sets, see Chapter 1).

  1. In this notes, we draw the incoming arrow of initial states in red for readability.↩︎

  2. Notice that we are not asking for I and F to be disjoint, actually, often they will have a non-trivial intersection.↩︎

  3. This is only done to have a nice concise definition of B. Algorithmically, we only add states to Q' when we encounter them, that is when we have a transition to them.↩︎

  4. Two DFAs are isomorphic if up to renaming of vertices they are the same.↩︎