[Overview] [Previous] [Next]

Implementing an NFA

If you think of an automaton as a computer, how does it handle nondeterminism? There are two ways that this could, in theory, be done:
  1. When the automaton is faced with a choice, it always (magically) chooses correctly. We sometimes think of of the automaton as consulting an oracle which advises it as to the correct choice.
  2. When the automaton is faced with a choice, it spawns a new process, so that all possible paths are followed simultaneously.
The first of these alternatives, using an oracle, is sometimes attractive mathematically. But if we want to write a program to implement an nfa, that isn't feasible.

There are three ways, two feasible and one not yet feasible, to simulate the second alternative:

  1. Use a recursive backtracking algorithm. Whenever the automaton has to make a choice, cycle through all the alternatives and make a recursive call to determine whether any of the alternatives leads to a solution (final state).
  2. Maintain a state set or a state vector, keeping track of all the states that the nfa could be in at any given point in the string.
  3. Use a quantum computer. Quantum computers explore literally all possibilities simultaneously. They are theoretically possible, but are at the cutting edge of physics. It may (or may not) be feasible to build such a device.
    Copyright © 1996 by David Matuszek
    Last modified Jan 29, 1996