** Next:** Constructing a DFA from
** Up:** REGULAR LANGUAGES
** Previous:** Converting a NFA to
** Contents**

NFAs are useful, in that they are easily constructed from regular expressions, and give us
some kind of computational idea of how a scanner might work. However, since they involve
making decisions, and backtracking if that decision was wrong, they are not really suitable
for implementation using conventional programming languages.

Instead, we use a **Deterministic Finite-State Automaton** (DFA) which is a special case of a
NFA with the additional requirements that:

- There are no transitions involving
- No state has two outgoing transitions based on the same symbol

Thus, when we are in some state in a DFA, there is no choice to be
made; the operation of a DFA can very easily be converted into a
program.

It is vital to note that: **every NFA can be converted to an
equivalent DFA**

We will define an algorithm to do this, for arbitrary NFAs; the basic
idea here is that sets of states in the NFA will correspond to just
one state in the DFA.

**Subsections**

** Next:** Constructing a DFA from
** Up:** REGULAR LANGUAGES
** Previous:** Converting a NFA to
** Contents**
James Power
2002-11-29