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
- Background Topics
- Formal Definition
- For now, I defer the formal definition of an NFA to the
textbook (pages 86-95).
- 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
- We can view a nondeterministic computation
(figure) as a
directed acyclic graph
of configurations indexed by time.
- 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.
- Comments
- Note the asymmetry between acceptance and rejection (there exists
and for all)
- 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.
- Why do we study this unrealistic model of computation?
- For now, our main reason for studying NFAs is that they
help us prove that the language classes LFSA and regular
languages are identical.
- In some cases, an NFA reveals the structure of a language
more clearly than an FA (example 5.2 on page 87).
- 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.
Table of Contents (up one level)
