Preface

Contents

Index

Glossary

Models

Rogues

Nondeterministic Finite State Automata

As a diagram, a nondeterministic finite state automaton looks no different than a deterministic finite state automaton. It is simply a directed, labeled graph.  The only difference is that there can be more than one arrow leading from a state with the same label (the nondeterminism).

Example 1.

There are many ways to visualize an nfa.  One is to think of the nfa as having each possible state it may be in colored a particular way.  As the next input symbol is processed, the currently colored states are uncolored, and the next states are colored according to how each currently colored state responds to the input.  Following is an example of an nfa that determines whether an arbitrary binary string ends in with 101 or 110.

Notice how nondeterminism is used.  Each time the automaton sees a 1 while in the first state, it considers that this might be the start of the last three symbols in the string (of course it doesn't know that).  So, it nondeterministically begins to check for a 101 or a 110.  Notice how a nondeterministic computation just "disappears" if it is found to be on the wrong track.