Martin

There is a close resemblance between the diagram in Figure 3.7 and the regular expression $(aa+aab)^*b$. The top loop corresponds to $aa$, the bottom one corresponds to $aab$, and the remaining $b$-transition corresponds to the last $b$ in the regular expression. To the extent that we think of it as a transition diagram like that of an FA, its resemblance to the regular expression suggests that the string $aaaabaab$, for example, should be accepted, because it allows us to start at $q_0$, take the top loop once, the bottom loop once, the top loop again, and finish up with the transition to the accepting state.

This diagram, however, is not the transition diagram for an FA, because there are three transitions from $q_0$ and fewer than two from several other states. The input string $aaaabaab$ allows us to reach the accepting state, but it also allows us to follow, or at least start to follow, other paths that don’t result in acceptance. We can imagine an idealized “device” that would work by using the input symbols to follow paths shown in the diagram, making arbitrary choices at certain points. It has to be nondeterministic, in the sense that the path it follows is not determined by the input string. (If the first input symbol is $a$, it chooses whether to start up the top path or down the bottom one.) Even if there were a way to build a physical device that acted like this, it wouldn’t accept this language in the same way that an FA could. Suppose we watched it process a string $x$. If it ended up in the accepting state at the end, we could say that $x$ was in the language; if it didn’t, all we could say for sure is that the moves it chose to make did not lead to the accepting state.

Allowing nondeterminism, by relaxing the rules for an FA, makes it easy to draw diagrams corresponding to regular expressions. However, we should no longer think of the diagram as representing an explicit algorithm for accepting the language, because an algorithm refers to a sequence of steps that are determined by the input and would be the same no matter how many times the algorithm was executed on the same input.

If the diagram doesn’t represent an explicit accepting algorithm, what good is it? One way to answer this is to think of the diagram as describing a number of different sequences of steps that might be followed. We can visualize these sequences for the input string $aaaabaab$ by drawing a computation tree, pictured in Figure 3.8.

A level of the tree corresponds to the input (the prefix of the entire input string) read so far, and the states appearing on this level are those in which the device could be, depending on the choices it has made so far. Two paths in the tree, such as the one that starts by treating the initial $a$ as the first symbol of $aab$, terminate prematurely, because the next input symbol does not allow a move from the current state. One path, which corresponds to interpreting the input string as $(aa)(aab)(aab)$, allows all the input to be read and ends up in a nonaccepting state. The path in which the device makes the “correct” choice at each step ends up at the accepting state when all the input symbols have been read.

If we had the transition diagram in Figure 3.7 and were trying to use it to accept the language, we could systematically keep track of the current sequence of steps, and use a backtracking strategy whenever we couldn’t proceed any further or finished in a nonaccepting state. The result would, in effect, be to search the computation tree using a depth-first search. In the next section we will see how to develop an ordinary finite automaton that effectively executes a breadth-first search of the tree, by keeping track after each input symbol of all the possible states the various sequences of steps could have led us to.

In this example we consider the regular expression $(aab)^*(a+aba)^*$. The techniques of Example 3.6 don’t provide a simple way to draw a transition diagram related to the regular expression, but Figure 3.10 illustrates another type of nondeterminism that does.

The new feature is a “$\Lambda$-transition,” which allows the device to change state with no input. If the input $a$ is received in state 0, there are three options: take the transition from state 0 corresponding to the $a$ in $aab$; move to state 3 and take the transition corresponding to $a$; and move to state 3 and take the transition corresponding to the $a$ in $aba$. The diagram shows two $a$-transitions from state 3, but because of the $\Lambda$-transition, we would have a choice of moves even if there were only one.

Figure 3.11 shows a computation tree illustrating the possible sequences of moves for the input string $aababa$. The $\Lambda$-transition is drawn as a horizontal arrow, so that as in the previous example, a new level of the tree corresponds to a new input symbol.

The string is accepted, because the device can choose to take the first loop, execute the $\Lambda$-transition, and take the longer loop from state 3.

The transition diagrams in our first two examples show four of the five ingredients of an ordinary finite automaton. The one that must be handled differently is the transition function $\delta$. For a state $q$ and an alphabet symbol $\sigma$, it is no longer correct to say that $\delta(q,\sigma)$ is a state: There may be no transitions from state $q$ on input $\sigma$, or one, or more than one. There may also be $\Lambda$-transitions. We can incorporate both of these features by making two changes: first, enlarging the domain of $\delta$ to include ordered pairs $(q,\Lambda)$ as well as the pairs in $Q\times\Sigma$; and second, making the values of $\delta$ sets of states instead of individual states.

A nondeterministic finite automaton (NFA) is a 5-tuple $(Q,\Sigma,q_0,A,\delta)$, where

• $Q$ is a finite set of states;
• $\Sigma$ is a finite input alphabet;
• $q_0\in Q$ is the initial state;
• $A\subseteq Q$ is the set of accepting states;
• $\delta:Q\times(\Sigma\cup\{\Lambda\})\to2^Q$ is the transition function.

For every element $q$ of $Q$ and every element $\sigma$ of $\Sigma\cup\{\Lambda\}$, we interpret $\delta(q,\sigma)$ as the set of states to which the FA can move, if it is in state $q$ and receives the input $\sigma$, or, if $\sigma=\Lambda$, the set of states other than $q$ to which the NFA can move from state $q$ without receiving any input symbol.

In Example 3.9, for example, $\delta(0,a)=\{1\}$, $\delta(0,\Lambda)=\{3\}$, $\delta(0,b)=\varnothing$, and $\delta(0,a)=\{3,4\}$.

In the case of an NFA $M=(Q,\Sigma,q_0,A,\delta)$, we want $\delta^*(q,x)$ to tell us all the states $M$ can get to by starting at $q$ and using the symbols in the string $x$. We can still define the function $\delta^*$ recursively, but the mathematical notation required to express this precisely is a little more involved, particularly if $M$ has $\Lambda$-transitions.

In order to define $\delta^*(q,x\sigma)$, where $x\in\Sigma^*$ and $\sigma\in\Sigma$, we start by considering $\delta^*(q,x)$, just as in the simple case of an ordinary FA. This is now a set of states, and for each state $p$ in this set, $\delta(p,\sigma)$ is itself a set. In order to include all the possibilities, we need to consider

Finally, we must keep in mind that in the case of $\Lambda$-transitions, “using all the symbols in the string $x$” really means using all the symbols in $x$ and perhaps $\Lambda$-transitions where they are possible. In the recursive step of the definition of $\delta^*$, once we have the union we have just described, we must consider all the additional states we might be able to reach from elements of this union, using nothing but $\Lambda$-transitions.

You can probably see at this point how the following definition will be helpful in our discussion.

Suppose $M=(Q,\Sigma,q_0,A,\delta)$ is an NFA, and $S\subseteq Q$ is a set of states. The $\Lambda$-closure of $S$ is the set $\Lambda(S)$ that can be defined recursively as follows.

1. $S\subseteq\Lambda(S)$.
2. For every $q\in\Lambda(S)$, $\delta(q,\Lambda)\subseteq\Lambda(S)$.

In exactly the same way as in Example 1.21, we can convert the recursive definition of $\Lambda(S)$ into an algorithm for evaluating it, as follows.

Initialize $T$ to be $S$. Make a sequence of passes, in each pass considering every $q\in T$ and adding to $T$ every state in $\delta(q,\Lambda)$ that is not already an element. Stop after the first pass in which $T$ is not changed. The final value of $T$ is $\Lambda(S)$. $\blacksquare$

A state is in $\Lambda(S)$ if it is an element of $S$ or can be reached from an element of $S$ using one or more $\Lambda$-transitions.

With the help of Definition 3.13 we can now define the extended transition function $\delta^*$ for a nondeterministic finite automaton.

Let $M=(Q,\Sigma,q_0,A,\delta)$ be an NFA. We define the extended transition function

as follows:

1. For every $q\in Q$, $\delta^*(q,\Lambda)=\Lambda(\{q\})$.
2. For every $q\in Q$, every $y\in\Sigma^*$, and every $\sigma\in\Sigma$,

A string $x\in\Sigma^*$ is accepted by $M$ if $\delta^*(q_0,x)\cap A\ne\varnothing$. The language $L(M)$ accepted by $M$ is the set of all strings accepted by $M$.

For the NFA in Example 3.9, which has only one $\Lambda$-transition, it is easy to evaluate $\delta^*(aababa)$ by looking at the computation tree in Figure 3.11. The two states on the first level of the diagram are 0 and 3, the elements of the $\Lambda$-closure of $\{0\}$. The states on the third level, for example, are 2, 3, and 4, because $\delta^*(0,aa)=\{2,3,4\}$. When we apply the recursive part of the definition to evaluate $\delta^*(0,aab)$, we first evaluate

and then we compute the $\Lambda$-closure of this set, which contains the additional element 3.

For an NFA $M$ with no $\Lambda$-transitions, both statements in the definition can be simplified, because for every subset $S$ of $Q$, $\Lambda(S)=S$.

We illustrate the definition once more in a slightly more extended example.

We start by evaluating the $\Lambda$-closure of the set $\{v\}$ in the NFA whose transition diagram is shown in Figure 3.16. When we apply the algorithm derived from Definition 3.13, after one pass $T$ is $\{v,w\}$, after two passes it is $\{v,w,q_0\}$, after three passes it is $\{v,w,q_0,p,t\}$, and during the next pass it remains unchanged. The set $\Lambda(\{s\})$ is therefore $\{v,w,q_0,p,t\}$.

If we want to apply the definition of $\delta^*$ to evaluate $\delta^*(q_0,aba)$, the easiest way is to begin with $\Lambda$, the shortest prefix of $aba$, and work our way up one symbol at a time.

The evaluation of $\Lambda(\{r,v\})$ is very similar to that of $\Lambda(\{v\})$, since there are no $\Lambda$-transitions from $r$, and the evaluation of $\Lambda(\{s,v,p,u\})$ is also similar. Because $\delta^*(q_0,aba)$ contains the accepting state $w$, the string $aba$ is accepted.

A state $r$ is an element of $\delta^*(q,x)$ if in the transition diagram there is a path from $q$ to $r$, in which there are transitions for every symbol in $x$ and the next transition at each step corresponds either to the next symbol in $x$ or to $\Lambda$. In simple examples, including this one, you may feel that it’s easier to evaluate $\delta^*$ by looking at the diagram and determining by inspection what states you can get to. One reason for having a precise recursive definition of $\delta^*$ and a systematic algorithm for evaluating it is that otherwise it’s easy to overlook things.