# Nondeterministic Finite State Automata (NFA)

#### Purpose

In this chapter, we define and describe an unusual extension to FSAs, the nondeterministic finite state automaton (NFA).

#### Topics

1. Background Topics
2. Formal Definition
• For now, I defer the formal definition of an NFA to the textbook (pages 86-95).

3. Intuitive ideas to supplement the formal definition
• What nondeterminism means:

• At the string level, a computation is not determined or cannot be completely specified by the NFA specification and the input string.

• At the configuration level, the next configuration is not determined or cannot be completely specified by the current state, the current input symbol, and the NFA specification.

• In contrast, both of these two concepts are deterministic when looking at FSAs.

• What is a nondeterministic computation?

• We viewed a deterministic computation (figure) as a sequence of configurations indexed by time.

• We can have two generalized views of nondeterministic computations

1. We can view a nondeterministic computation (figure) as a directed acyclic graph of configurations indexed by time.

2. Alternatively, we can still view a nondeterministic computation (figure) as a sequence of configurations.

• In this case, we need to record a set of states that the NFA might be in instead of recording a single state the NFA might be in.

• The second view will be useful when showing that any NFA can be transformed into an FSA.

• The first view is more useful when generalizing beyond FSAs to pushdown automata and Turing machines in later units.

• How do we interpret acceptance of a string x by an NFA N?

• Definition of acceptance and rejection
• Look at the set of configurations the NFA N is in at time |x| (this denotes the length of the string x).

• If the NFA is in an accepting state in any one of these configurations, we say that N accepts x; that is, if there exists a configuration at time |x| where the NFA is in an accepting state, we say that N accepts x.

• We say that an NFA N rejects x only if the above condition does not hold; that is, if all the configurations the NFA N is in at time |x| are rejecting configurations, then the NFA N rejects x.

• Also note that if we use the second view of a computation, we can think of an NFA N with n states dividing up * into 2n categories since there are 2n different possible sets of states for an NFA to be in at any given time.
• In a related vein, an NFA representation can be much more efficient since an NFA with n states can divide * into 2n categories whereas an FSA with n states can only divide * into n categories.