Martin

and if both $S$ and this set qualify as states in our new definition, then it sounds as though we have eliminated the nondeterminism. The only question then is whether the FA we obtain accepts the same strings as the NFA we started with.

For every language $L\subseteq\Sigma^*$ accepted by an NFA $M=(Q,\Sigma,q_0,A,\delta)$, there is an NFA $M_1$ with no $\Lambda$-transitions that also accepts $L$.

As we have already mentioned, we may need to add transitions in order to guarantee that the same strings will be accepted even when the $\Lambda$-transitions are eliminated. In addition, if $q_0\notin A$ but $\Lambda\in L$, we will also make $q_0$ an accepting state of $M_1$ in order to guarantee that $M_1$ accepts $\Lambda$. We define

where for every $q\in Q$, $\delta_1(q,\Lambda)=\varnothing$, and for every $q\in Q$ and every $\sigma\in\Sigma$,

Finally, we define

For every state $q$ and every $x\in\Sigma^*$, the way we have defined the extended transition function $\delta^*$ for the NFA $M$ tells us that $\delta^*(q,x)$ is the set of states $M$ can reach by using the symbols of $x$ together with $\Lambda$-transitions. The point of our definition of $\delta_1$ is that we want $\delta_1^*(q,x)$ to be the same set, even though $M_1$ has no $\Lambda$-transitions. This may not be true for $x=\Lambda$, because $\delta^*(q,\Lambda)=\Lambda(\{q\})$ and $\delta_1(q,\Lambda)=\{q\}$; this is the reason for the definition of $A_1$ above. We sketch the proof that for every $q$ and every $x$ with $|x|\ge1$,

The proof is by structural induction on $x$. If $x=a\in\Sigma$, then by definition of $\delta_1$, $\delta_1(q,x)=\delta^*(q,x)$, and because $M_1$ has no $\Lambda$-transitions, $\delta_1(q,x)=\delta_1^*(q,x)$ (see Exercise 3.24).

Suppose that for some $y$ with $|y|\ge1$, $\delta_1^*(q,y)=\delta^*(q,y)$ for every state $q$, and let $\sigma$ be an arbitrary element of $\Sigma$.

The last step in the induction proof is to check that this last expression is indeed $\delta^*(q,y\sigma)$. This is a special case of the general formula

See Exercise 3.30 for the details.

Now we can verify that $L(M_1)=L(M)=L$. If the string $\Lambda$ is accepted by $M$, then it is accepted by $M_1$, because in this case $q_0\in A_1$ by definition. If $\Lambda\notin L(M)$, then $A=A_1$; therefore, $q_0\notin A_1$, and $\Lambda\notin L(M_1)$.

Suppose that $|x|\ge1$. If $x\in L(M)$, then $\delta^*(q_0,x)$ contains an element of $A$; therefore, since $\delta^*(q_0,x)=\delta_1^*(q_0,x)$ and $A\subseteq A_1$, $x\in L(M_1)$.

Now suppose $|x|\ge1$ and $x\in L(M_1)$. Then $\delta_1^*(q_0,x)$ contains an element of $A_1$. The state $q_0$ is in $A_1$ only if $\Lambda\in L$; therefore, if $\delta_1^*(q_0,x)$ (which is the same as $\delta^*(q_0,x)$) contains $q_0$, it also contains every element of $A$ in $\Lambda(\{q_0\})$. In any case, if $x\in L(M_1)$, then $\delta_1^*(q_0,x)$ must contain an element of $A$, which implies that $x\in L(M)$.

For every language $L\subseteq\Sigma^*$ accepted by an NFA $M=(Q,\Sigma,q_0,A,\delta)$, there is an FA $M_1=(Q_1,\Sigma,q_1,A_1,\delta_1)$ that also accepts $L$.

Because of Theorem 3.17, it is sufficient to prove the theorem in the case when $M$ has no $\Lambda$-transitions. The formulas defining $\delta^*$ are simplified accordingly: $\delta^*(q,\Lambda)=\{q\}$ and $\delta^*(q,x\sigma)=\bigcup\{\delta(p,\sigma)\mid p\in\delta^*(q,x)\}$.

The finite automaton $M_1$ can be defined as follows, using the subset construction: The states of $M_1$ are sets of states of $M$, or

The initial state $q_1$ of $Q_1$ is $\{q_0\}$. For every $q\in Q_1$ and every $\sigma\in\Sigma$,

and the accepting states of $M_1$ are defined by the formula

The last definition is the correct one, because a string $x$ should be accepted by $M_1$ if, when the NFA $M$ processes $x$, there is at least one state it might end up in that is an element of $A$.

There is no doubt that $M_1$ is an ordinary finite automaton. The expression $\delta_1^*(q_1,x)$, however, is a set of states of $M$—not because $M_1$ is nondeterministic, but because we have defined states of $M_1$ to be sets of states of $M$. The fact that the two devices accept the same language follows from the fact that for every $x\in\Sigma^*$,

and we now prove this formula using structural induction on $x$. We must keep in mind during the proof that $\delta_1^*$ and $\delta^*$ are defined in different ways, because $M_1$ is an FA and $M$ is an NFA.

If $x=\Lambda$, then

The induction hypothesis is that $x$ is a string for which $\delta_1^*(q_1,x)=\delta^*(q_0,x)$, and we must show that for every $\sigma\in\Sigma$, $\delta_1^*(q_1,x\sigma)=\delta^*(q_0,x\sigma)$.

A string $x$ is accepted by $M_1$ precisely if $\delta_1^*(q_1,x)\in A_1$. We know now that this is true if and only if $\delta^*(q_0,x)\in A_1$; and according to the definition of $A_1$, this is true if and only if $\delta^*(q_0,x)\cap A\ne\varnothing$. Therefore, $x$ is accepted by $M_1$ if and only if $x$ is accepted by $M$.

We present three examples: one that illustrates the construction in Theorem 3.17, one that illustrates the subset construction in Theorem 3.18, and one in which we use both to convert an NFA with $\Lambda$-transitions to an ordinary FA.

Figure 3.20a shows the transition diagram for an NFA $M$ with $\Lambda$-transitions; it is not hard to see that it accepts the language corresponding to the regular expression $(a^*ab(ba)^*)^*$. We show in tabular form the values of the transition function $\delta$, as well as the values $\delta^*(q,a)$ and $\delta^*(q,b)$ that will give us the transition function $\delta_1$ in the resulting NFA $M_1$.

For example, the value $\delta^*(5,a)$ is the set $\{1,2,4\}$, because $\delta(5,a)=\{4\}$ and there are $\Lambda$-transitions from 4 to 1 and from 1 to 2.

Figure 3.20b shows the NFA $M_1$, whose transition function has the values in the last two columns of the table. In this example, the initial state of $M$ is already an accepting state, and so drawing the new transitions and eliminating the $\Lambda$-transitions are the only steps required to obtain $M_1$.

We consider the NFA $M=(Q,\{a,b\},0,A,\delta)$ in Example 3.6, shown in Figure 3.7. Instead of labeling states as $q_i$, here we will use only the subscript $i$. We will describe the FA $M_1=(2^Q,\{a,b\},\{0\},A_1,\delta_1)$ obtained from the construction in the proof of Theorem 3.18. Because a set with $n$ elements has $2^n$ subsets, using this construction might require an exponential increase in the number of states. As this example will illustrate, we can often get by with fewer by considering only the states of $M_1$ (subsets of $Q$) that are reachable from $\{0\}$, the initial state of $M_1$.

It is helpful, and in fact recommended, to use a transition table for $\delta$ in order to obtain the values of $\delta_1$. The table is shown below.

The transition diagram for $M_1$ is shown in Figure 3.22. For example, $\delta_1(\{1,2\},a)=\delta(1,a)\cup\delta(2,a)=\{0,3\}$. If you compare Figure 3.22 to Figure 2.23c, you will see that they are the same except for the way the states are labeled. The subset construction doesn’t always produce the FA with the fewest possible states, but in this example it does.

For the NFA pictured in Figure 3.24a, we show the transition function in tabular form below, as well as the transition function for the resulting NFA without $\Lambda$-transitions. It is pictured in Figure 3.24b.

The subset construction gives us a slightly greater variety of subsets this time, but still considerably fewer than the total number of subsets of $Q$. The final FA is shown in Figure 3.24c.