Let's formalize what an NFA is.
A nondeterministic finite automaton (NFA) is a 5-tuple $A = (Q,\Sigma,\delta,I,F)$, where
This looks basically the same as the DFA, except for one important difference: the transition function $\delta$ is now a function from a state and a symbol to a set of states. This explains why we don't require that $\delta$ is defined explicitly for all states and symbols. Since the image of $\delta$ is sets of $Q$, we implicitly define "missing" transitions as going to the empty set $\emptyset$.
Notice also that we have a set of initial states. This change actually isn't that important—it's possible to define NFAs using only one initial state and it doesn't change very much (you might want to try proving this on your own).
Here is our NFA from last class, which we claim accepts all strings with a $b$ in the third-to-last position.
The formal definition of this NFA would be $A = (Q,\Sigma,\delta,I,F)$ where
and the transition function $\delta$ is defined by
| $a$ | $b$ | |
|---|---|---|
| $q_0$ | $\{q_0\}$ | $\{q_0, q_1\}$ |
| $q_1$ | $\{q_2\}$ | $\{q_2\}$ |
| $q_2$ | $\{q_3\}$ | $\{q_3\}$ |
| $q_3$ | $\emptyset$ | $\emptyset$ |
One way to think about nondeterminism is to think of every nondeterministic transition as a possible choice. For instance, if we're in $q_0$ and we see a $b$, our choice is between staying in $q_0$ or going to $q_1$. We would not have such a choice in a determinstic machine. But how do we think about the ability to choose which path to take? To do this, we need to formally define acceptance for nondeterministic machines.
Again, we will extend our transition function, but this time we will do so in two ways. First, we'll do the same thing we did for DFAs, which is to extend $\delta$ to a function on strings $\delta^*: Q \times \Sigma^* \to 2^Q$. We define $\delta^*(q,\varepsilon) = \{q\}$ and for $w = xa$ with $x \in \Sigma^*$ and $a \in \Sigma$, we have $$ \delta^*(q,xa) = \bigcup_{p \in \delta^*(q,x)} \delta(p,a).$$
As usual, we drop the star when the context is clear that we're working with strings. The other extension we'll make is more of a convenience (or an abuse of notation) by treating $\delta$ as a function on subsets of states $\delta: 2^Q \times \Sigma^* \to 2^Q$. To do this, we take for $P \subseteq Q$, $$\delta(P,a) = \bigcup_{q \in P} \delta(q,a)$$ when the context is clear.
Let's take a moment to see how this definition fits with our intution about how nondeterminism behaves. It is easy to see that by taking the union of these sets, we really do get all possible transitions. However, note that this definition also handles transitions that are missing: if $\delta(p,a) = \emptyset$, then for any set $S$, we have $S \cup \emptyset = S$, and so $\delta^*$ remains well-defined.
Now, we can define acceptance under the nondeterministic model.
We say that an NFA $A$ accepts a word $w$ if $\delta^*(i,w) \cap F \neq \emptyset$ for some initial state $i \in I$. Then the language of an NFA $A = (Q,\Sigma,\delta,I,F)$ is defined by $$ L(A) = \left\{w \in \Sigma^* \mid \delta^*(I,w) \cap F \neq \emptyset \right\}.$$
What does this definition say? For DFAs, acceptance is defined as the machine being in a final state at the moment we finish reading our input string. For NFAs, we will be in multiple possible states when we finish reading our string. This definition of acceptance says that as long as there is a final state among these states, the NFA accepts the string.
If we think of nondeterminic transitions as a choice, then a nondeterministic machine explores all possible choices we could have made. One way to interpret what the acceptance condition is saying is that as long as there is at least one set of choices that we can make so that we're in a final state, then our string is accepted.
Another way to interpret nondeterministic choices is rather than making a choice, we're really making a guess: we don't know which of the choices we make are the right ones. But as long as there is some choice that works, then we can guess at each step and come up with a valid accepting computation.
The ability to guess is exactly what we need in order to solve the concatenation problem: with a deterministic machine, our problem was we didn't know when to make the jump from the first part of the string to the second part of the string. Without the ability to double back and re-read the front of the string, we need to be able to guess when the "break" happens.
Let $L_1$ and $L_2$ be DFA languages. Then there exists an NFA that accepts $L_1L_2$.
Let $L_1$ and $L_2$ be languages that are recognized by 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)$, respectively. We will construct an NFA $A' = (Q',\Sigma, \delta', I', F')$ to recognize $L_1 L_2$. Here, we have
What does this NFA do? We begin by reading our string on $A_1$. Then, whenever the machine enters a final state of $A_1$, it simultaneously enters the initial state of $A_2$. In this way, we nondeterministically "guess" that we start the second part of the string. Then this construction hinges on the observation that we can only make it into the automaton $A_2$ if we enter a final state of $A_1$.
Consider a word $w \in \Sigma^*$ that's accepted by $A'$—that is $w \in L(A')$. Then $\delta'(\{q_{0,a}\}, w) \cap F_2 \neq \emptyset$. So we can split the word up into two words $w = xy$. Since the only entry point into $A_2$ is $q_{0,2}$, we have that $\delta_2(q_{0,2},y) \in F_2$. But in order for $q_{0,2}$ to be reached, there had to be some word $x$ such that $\delta_1(q_{0,1},x) \in F_1$. Our computation path looks like \begin{align*} q_{0,1} \xrightarrow{x} p \in & F_1, \\ & q_{0,2} \xrightarrow{y} q \in F_2 \end{align*} This gives us our two words $x \in L(A_1)$ and $y \in L(A_2)$ and therefore $w = xy \in L_1L_2$.
Now, suppose that $w \in L_1L_2$. This means that $w = uv$ where $u \in L_1$ and $v \in L_2$, and since these languages are both accepted by their respective DFAs, we have $u \in L(A_1)$ and $v \in L(A_2)$. So $\delta_1(q_{0,1}, w) = q \in F_1$ and $\delta_2(q_{0,2}, v) = q' \in F_2$. Then in $A'$, we have $\{q, q_{0,2}\} \subseteq \delta'(\{q_{0,1}\}, u)$. We then have $\delta'(\{q,q_{0,2}\}, v) \subseteq \delta'(\{q_{0,1}\}, uv)$ and therefore $\delta'(\{q_{0,1}\}, uv) \cap F_2 \neq \emptyset$. \begin{align*} q_{0,1} \xrightarrow{u} q \in & F_1, \\ & q_{0,2} \xrightarrow{v} q' \in F_2 \end{align*} So $w = uv \in L(A')$.