Next: Definition of NFA
Up: No Title
Previous: Acceptance
- play central role in language theory
- for some models, deterministic & nondeterministic versions
are equivalent in power. For others, they are not. For a few, this question
is deep (eg. P ?= NP).
Figure 1: An NFA for 
.
- Acceptance:
is accepted by an NFA, if there exists
a sequence of transitions from 
to a state 
on .
Sushil Prasad
Tue Jul 7 12:26:32 EDT 1998