11.3.2 Nondeterministic Finite Automata

An interesting connection lies between the ideas of this chapter and the theory of finite automata, which is part of the theory of computation (see [462,891]). In Section 2.1, it was mentioned that determining whether there exists some string that is accepted by a DFA is equivalent to a discrete feasible planning problem. If unpredictability is introduced into the model, then a nondeterministic finite automaton (NFA) is obtained, as depicted in Figure 11.8. This represents one of the simplest examples of nondeterminism in theoretical computer science. Such nondeterministic models serve as a powerful tool for defining models of computation and their associated complexity classes. It turns out that these models give rise to interesting examples of information spaces.

Figure 11.8: (a) An nondeterministic finite automaton (NFA) is a state machine that reads an input string and decides whether to accept it. (b) A graphical depiction of an NFA.

An NFA is typically described using a directed graph as shown in Figure 11.8b, and is considered as a special kind of finite state machine. Each vertex of the graph represents a state, and edges represent possible transitions. An input string of finite length is read by the machine. Typically, the input string is a binary sequence of 0's and $1$'s. The initial state is designated by an inward arrow that has no source vertex, as shown pointing into state $a$ in Figure 11.8b. The machine starts in this state and reads the first symbol of the input string. Based on its value, it makes appropriate transitions. For a DFA, the next state must be specified for each of the two inputs 0 and $1$ from each state. From a state in an NFA, there may be any number of outgoing edges (including zero) that represent the response to a single symbol. For example, there are two outgoing edges if 0 is read from state $c$ (the arrow from $c$ to $b$ actually corresponds to two directed edges, one for 0 and the other for $1$). There are also edges designated with a special $\epsilon$ symbol. If a state has an outgoing $\epsilon$, the state may immediately transition along the edge without reading another symbol. This may be iterated any number of times, for any outgoing $\epsilon$ edges that may be encountered, without reading the next input symbol. The nondeterminism arises from the fact that there are multiple choices for possible next states due to multiple edges for the same input and $\epsilon$ transitions. There is no sensor that indicates which state is actually chosen.

The interpretation often given in the theory of computation is that when there are multiple choices, the machine clones itself and one copy runs each choice. It is like having multiple universes in which each different possible action of nature is occurring simultaneously. If there are no outgoing edges for a certain combination of state and input, then the clone dies. Any states that are depicted with a double boundary, such as state $a$ in Figure 11.8, are called accept states. When the input string ends, the NFA is said to accept the input string if there exists at least one alternate universe in which the final machine state is an accept state.

The formulation usually given for NFAs seems very close to Formulation 2.1 for discrete feasible planning. Here is a typical NFA formulation [891], which formalizes the ideas depicted in Figure 11.8:

Formulation 11..2 (Nondeterministic Finite Automaton)  

1. A finite state space $X$.
2. A finite alphabet $\Sigma$ which represents the possible input symbols. Let $\Sigma_\epsilon = \Sigma \cup \{\epsilon\}$.
3. A transition function, $\delta : X \times \Sigma_\epsilon \rightarrow {\rm pow}(X)$. For each state and symbol, a set of outgoing edges is specified by indicating the states that are reached.
4. A start state $x_0 \in X$.
5. A set $A \subseteq X$ of accept states.

Example 11..18 (Three-State NFA)   The example in Figure 11.8 can be expressed using Formulation 11.2. The components are $X = \{a,b,c\}$, $\Sigma = \{0,1\}$, $\Sigma_\epsilon = \{0,1,\epsilon\}$, $x_0 = a$, and $A = \{a\}$. The state transition equation requires the specification of a state for every $x \in X$ and symbol in $\Sigma_\epsilon$:

$$\begin{tabular}{c\vert ccc} & $0$ & $1$ & $\epsilon$ \hline... ... $\emptyset$ $c$ & $\{b,c\}$ & $\{b\}$ & $\emptyset$ . \end{tabular}$$ (11.47)

$\blacksquare$

Now consider reformulating the NFA and its acceptance of strings as a kind of planning problem. An input string can be considered as a plan that uses no form of feedback; it is a fixed sequence of actions. The feasible planning problem is to determine whether any string exists that is accepted by the NFA. Since there is no feedback, there is no sensing model. The initial state is known, but subsequent states cannot be measured. The history I-state ${\eta}_k$ at stage $k$ reduces to ${\eta}_k = {\tilde{u}}_{k-1} = (u_1,\ldots,u_{k-1})$, the action history. The nondeterminism can be accounted for by defining nature actions that interfere with the state transitions. This results in the following formulation, which is described in terms of Formulation 11.2.

Formulation 11..3 (An NFA Planning Problem)  

1. A finite state space $X$.
2. An action space $U = \Sigma \cup \{u_T\}$.
3. A state transition function, $F : X \times U \rightarrow {\rm pow}(X)$. For each state and symbol, a set of outgoing edges is specified by indicating the states that are reached.
4. An initial state $x_0 = x_1$.
5. A set ${X_{G}}= A$ of goal states.

The history I-space ${\cal I}_{hist}$ is defined using

$${{\cal I}_k}= {\tilde{U}}_{k-1}$$ (11.48)

for each $k \in {\mathbb{N}}$ and taking the union as defined in (11.19). Assume that the initial state of the NFA is always fixed; therefore, it does not appear in the definition of ${\cal I}_{hist}$.

For expressing the planning task, it is best to use the nondeterministic I-space ${\cal I}_{ndet}= {\rm pow}(X)$ from Section 11.2.2. Thus, each nondeterministic I-state, $X({\eta}) \in {\cal I}_{ndet}$, is the subset of $X$ that corresponds to the possible current states of the machine. The initial condition could be any subset of $X$ because $\epsilon$ transitions can occur from $x_1$. Subsequent nondeterministic I-states follow directly from $F$. The task is to compute a plan of the form

$$\pi = (u_1,u_2,\ldots,u_K,u_T) ,$$ (11.49)

which results in $X_{K+1}({\eta}_{K+1}) \in {\cal I}_{ndet}$ with $X_{K+1}({\eta}_{K+1}) \cap {X_{G}}\not = \emptyset$. This means that at least one possible state of the NFA must lie in ${X_{G}}$ after the termination action is applied. This condition is much weaker than a typical planning requirement. Using worst-case analysis, a typical requirement would instead be that every possible NFA state lies in ${X_{G}}$.

The problem given in Formulation 11.3 is not precisely a specialization of Formulation 11.1 because of the state transition function. For convenience, $F$ was directly defined, instead of explicitly requiring that $f$ be defined in terms of nature actions, $\Theta(x,u)$, which in this context depend on both $x$ and $u$ for an NFA. There is one other small issue regarding this formulation. In the planning problems considered in this book, it is always assumed that there is a current state. For an NFA, it was already mentioned that if there are no outgoing edges for a certain input, then the clone of the machine dies. This means that potential current states cease to exist. It is even possible that every clone dies, which leaves no current state for the machine. This can be easily enabled by directly defining $F$; however, planning problems must always have a current state. To resolve this issue, we could augment $X$ in Formulation 11.3 to include an extra dead state, which signifies the death of a clone when there are no outgoing edges. A dead state can never lie in ${X_{G}}$, and once a transition to a dead state occurs, the state remains dead for all time. In this section, the state space will not be augmented in this way; however, it is important to note that the NFA formulation can easily be made consistent with Formulation 11.3.

The planning model can now be compared to the standard use of NFAs in the theory of computation. A language of an NFA is defined to be the set of all input strings that it accepts. The planning problem formulated here determines whether there exists a string (which is a plan that ends with termination actions) that is accepted by the NFA. Equivalently, a planning algorithm determines whether the language of an NFA is empty. Constructing the set of all successful plans is equivalent to determining the language of the NFA.

Example 11..19 (Planning for the Three-State NFA)   The example in Figure 11.8 can be expressed using Formulation 11.2. The components are $X = \{a,b,c\}$, $\Sigma = \{0,1\}$, $\Sigma_\epsilon = \{0,1,\epsilon\}$, $x_0 = a$, and $F = \{a\}$. The function $F(x,u)$ is defined as

$$\begin{tabular}{c\vert cc} & $0$ & $1$ \hline $a$ & $\empty... ...$ & $\{a,b\}$ & $\emptyset$ $c$ & $\{b,c\}$ & $\{b\}$. \end{tabular}$$ (11.50)

The nondeterministic I-space is

$$X({\eta}) = \{\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\} \} ,$$ (11.51)

in which the initial condition is ${\eta_0}= \{a,b\}$ because an $\epsilon$ transition occurs immediately from $a$. An example plan that solves the problem is $(1,0,0,u_T,\ldots)$. This corresponds to sending an input string ``$100$'' through the NFA depicted in Figure 11.8. The sequence of nondeterministic I-states obtained during the execution of the plan is

$$\{a,b\} \stackrel{1}{\rightarrow} \{c\} \stackrel{0}{\rightarrow}... ...c\} \stackrel{0}{\rightarrow} \{a,b,c\} \stackrel{u_T}{\rightarrow} \{a,b,c\} .$$ (11.52)

$\blacksquare$

A basic theorem from the theory of finite automata states that for the set of strings accepted by an NFA, there exists a DFA (deterministic) that accepts the same set [891]. This is proved by constructing a DFA directly from the nondeterministic I-space. Each nondeterministic I-state can be considered as a state of a DFA. Thus, the DFA has $2^n$ states, if the original NFA has $n$ states. The state transitions of the DFA are derived directly from the transitions between nondeterministic I-states. When an input (or action) is given, then a transition occurs from one subset of $X$ to another. A transition is made between the two corresponding states in the DFA. This construction is an interesting example of how the I-space is a new state space that arises when the states of the original state space are unknown. Even though the I-space is usually larger than the original state space, its states are always known. Therefore, the behavior appears the same as in the case of perfect state information. This idea is very general and may be applied to many problems beyond DFAs and NFAs; see Section 12.1.2