Recall that languages are just sets of words and that we can perform set operations on languages. However, once we start thinking about computation, particularly with our simple model of computation, an important question is whether the resulting language that we get from applying these operations is still computable.
What does applying these operations allow us to do? Consider the boolean set operations. If we took one of the problems we've seen, like divisibility by 3 or searching for a substring, we can use the boolean set operations to express natural followup questions:
We say that a class of languages is closed under an operation if whenever the arguments of the operation are in the class, the result is also.
Let's consider the DFA languages. If we want to show that the DFA languages are closed under a particular operation, we have to show that the result of the operation can be recognized by a DFA. The most straightforward way of doing this is to take the input DFAs and use them to construct a DFA for the result—an algorithm.
First, let's do a simple, but very useful, example.
The DFA languages are closed under complement.
Proof. Let $L \subseteq \Sigma^*$ be a DFA language. Since $L$ is DFA, it is recognized by a DFA $A = (Q,\Sigma^*,\delta,q_0,F)$. We will construct a DFA $A'$ that recognizes $\overline L$ as follows: let $A' = (Q,\Sigma,\delta,q_0,Q \setminus F)$.
In other words, we take the DFA $A$ and swap the set of non-final and final states. Then we have for all $w \in \Sigma^*$, \begin{align*} w \in L(A') &\iff \delta(q_0,w) \in Q \setminus F \\ &\iff w \not \in L(A) \\ &\iff w \not \in L \\ &\iff w \in \overline L \end{align*} $\tag*{$\Box$}$
If we think back to languages as decision problems, then this gives us a handy way to solve the complement of some problems. For instance, we now have a very easy way to determine whether a number isn't divisible by 3.
Obviously, we are very interested in the closure properties for the basic set operations (union, intersection, complement) and the basic string operations (concatenation, Kleene star). These give us ways to combine and solve problems that we already know how to solve. First, let's consider the intersection.
Suppose we have two DFA languages, $L_1$ and $L_2$. Since they're DFA, we know that they can be recognized by some DFA, say $A_1$ and $A_2$. By definition, if $w \in L_1 \cap L_2$, then this means $w \in L_1$ and $w \in L_2$. Conceptually, all we need to do is run $A_1$ on $w$ and run $A_2$ on $w$ and see if it's accepted by both. This idea of running two machines in parallel leads us to the product construction.
Consider DFAs $A_1 = (Q_1, \Sigma, \delta_1, q_{0,1}, F_1)$ and $A_2 = (Q_2, \Sigma, \delta_2, q_{0,2}, F_2)$. Then the product automaton of $A_1$ and $A_2$ is the DFA $A' = (Q',\Sigma,\delta',q_0',F')$, where
In the product automaton, every state is a pair of states, with one from $A_1$ and the other from $A_2$. This way, we can keep track of the computation on the word $w$ for each of our automata. The set of accepting states for $A'$ are those pairs with an accepting state from each machine. In other words, $A'$ will accept only when $w$ reaches a final state in $A_1$ and a final state in $A_2$.
Why is this called the product automaton? Notice that the states of the automaton are the cartesian product of the state sets of the two DFAs we started out with. So we can think of the product automaton as being the cartesian product of two DFAs. Of course, we have to make sure that the transition function still makes sense.
So let's prove formally that the product construction works. First, we'll show that the transition function behaves pretty much how we'd expect it to.
For all $w \in \Sigma^*$, \[\delta'(\langle p,q \rangle, w) = \langle \delta_1(p,w), \delta_2(q,w) \rangle.\]
We will prove this by induction on $w$.
For the base case, we have $w = \varepsilon$. Then $$\delta'(\langle p,q \rangle, \varepsilon) = \langle p,q \rangle = \langle \delta_1(p,\varepsilon, \delta_2(q, \varepsilon) \rangle.$$
Then for our inductive step, we let $w = xa$ for $a \in \Sigma$ and $x \in \Sigma^*$ and assume that $\delta'(\langle p,q \rangle, x) = \langle \delta_1(p,x), \delta_2(q,x) \rangle$. We have \begin{align*} \delta'(\langle p,q \rangle, xa) &= \delta'(\delta'(\langle p,q \rangle, x),a) \\ &= \delta'(\langle \delta_1(p,x), \delta_2(q,x) \rangle,a) \\ &= \langle \delta_1(\delta_1(p,x),a), \delta_2(\delta_2(q,x),a) \rangle \\ &= \langle \delta_1(p,xa), \delta_2(q,xa) \rangle \end{align*}
Now, we'll prove that our automaton accepts the intersection like we want.
$L(A') = L_1 \cap L_2$.
Let $w \in \Sigma^*$. Then, \begin{align*} w \in L(A') &\iff \delta'(q_0',w) \in F' \\ &\iff \delta'(\langle q_{0,1}, q_{0,2} \rangle, w) \in F_1 \times F_2 \\ &\iff \langle \delta_1(q_{0,1},w), \delta_2(q_{0,2},w) \rangle \in F_1 \times F_2 \\ &\iff \delta_1(q_{0,1},w) \in F_1 \text{ and } \delta_2(q_{0,2},w) \in F_2 \\ &\iff w \in L(A_1) \text{ and } w \in L(A_2) \\ &\iff w \in L_1 \text{ and } w \in L_2 \\ &\iff w \in L_1 \cap L_2 \end{align*}
The class of DFA languages is closed under intersection.
The product construction is a construction due to Rabin and Scott in 1959. We will see this paper pop up again—a lot of fundamental results about finite automata come from here.
Now, let's consider union. If we think about our approach to intersection, we can see that it's not actually that different. Instead of accepting a word when both automata accept it, we can modify our final state set so that a word is accepted when at least one of the automata accept. Then such a DFA follows the product construction from above, with the difference being the set of final states, $$F' = (F_1 \times Q_2) \cup (Q_1 \times F_2).$$ This set consists of all pairs that contain a final state of $A_1$ or a final state of $A_2$.
However, there is another easy but slightly indirect way. We can make use of the closure properties we've already proved so far.
The class of DFA languages is closed under union.
Let $L_1$ and $L_2$ be languages recognized by DFAs. Then $\overline{L_1}$ and $\overline{L_2}$ are also recognized by DFAs, by Theorem 3.3. Since DFA languages are closed under intersection, by Theorem 4.2, $\overline{L_1} \cap \overline{L_2}$ is also a DFA language. But this language is $\overline{L_1 \cup L_2}$ by De Morgan's laws. And since DFA languages are closed under complementation, $L_1 \cup L_2$ must also be a DFA language.
We can do the same kind of thing for other similar set operations like set difference. But what about an entirely different kind of operation like concatenation? We can define many more interesting string operations, like concatenation, and ask whether those operations preserve the property of being recognizable by DFAs.
Here are some examples of string and language operations.
But before we get to any of those, let's think about whether we can come up with a DFA for concatenation. We can imagine that if we wanted to recognize a word $uv$, where $u \in L_1$ and $v \in L_2$, what we could do is check that $u$ is accepted by the DFA $A_1$ for $L_1$ and $v$ is accepted by the DFA $A_2$ for $L_2$. Then rather than running the two machines in parallel, we'd run them one after the other.
There is a problem with this approach: when we give a DFA a word $uv$, it doesn't actually know where $u$ ends and $v$ begins. An obvious idea to fix this would be to test whether a state was a final state in $A_1$, but this only gets us so far.
Consider the following scenario where we have a word $uvw$, where $u, uv \in L_1$ and $w \in L_2$ but $vw \not \in L_2$. In this case, our DFA could see that $u$ brings us to a final state of $A_1$ and start processing $vw$ on $A_2$, only to reject $vw$.
The big problem is that our transitions have to be uniquely determined, but we can't go back and try something else. In other words, we have to know exactly where we're going. And so, we seem to be hitting our first roadblock.
As DFAs are currently defined (and so named) the transition function $\delta$ is deterministic. That is, the next state is uniquely determined by the current state and input symbol, or there is exactly one state that the transition function points to. This keeps things simple for us and it accurately reflects how real computers work. However, it does seem like a bit of a stifling restriction and sometimes there are a few points where it'd be so much easier just to be able to go to multiple states.
Here, we'll relax the condition that the transition function is deterministic by introducing nondeterminism to finite automata. We call these machines nondeterministic finite automata for obvious reasons. Informally, this means that in an NFA, for each state and transition symbol, we'll allow transitions to multiple states.
The following is an example of an NFA, which accepts the language $\{a,b\}^* b \{a,b\}^2$. Note that on $q_0$, there are two transitions on $b$: one to $q_0$ and one to $q_1$.
Conceptually, what does this mean? In essence, the NFA can "guess" which transition to take. While with a DFA we could represent a computation on an input word with a single path, with nondeterminism, there are multiple paths which we can represent as a tree, with branches forming at the points where there are choices to be made.
But if there are multiple possible paths, how do we define acceptance under this model? If there is at least one path which, after reading the input word, reaches an accepting state, then the NFA accepts the word. This fits with the idea that the NFA makes guesses whenever it has a choice; the existence of a path that reaches a final state means that there is a set of guesses that the NFA could make in order for the word to be accepted. Conversely, the NFA rejects $w$ if there are no paths which reach a final state upon reading $w$.