- 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.

- At the string level, a computation is
- 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.

- In this case, we need to record a

- We can view a nondeterministic computation
(figure) as a
- 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.

- We viewed a deterministic computation
(figure)
as a
- 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 2^{n}categories since there are 2^{n}different possible sets of states for an NFA to be in at any given time.

- Note the asymmetry between acceptance and rejection (there exists
and for all)

- 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 2^{n}categories whereas an FSA with*n*states can only divide^{*}into*n*categories.

- For now, our main reason for studying NFAs is that they
help us prove that the language classes LFSA and regular
languages are identical.