Our First Look at a Nondeterministic Finite State Automaton

Our first example of a nondeterministic finite state automaton (NFSA) is one that recognizes all of the binary strings that end in 101.  This example is a good one to start with because it highlights a situation in which an NSFA is probably easier to understand than an equivalent DFSA. You may remember that we have already seen a DFSA that recognizes all of the binary strings that end in 101.  It looked like this:

The trick to designing the DFSA for the set of binary strings that end in 101 is that there is no way that the a DFSA can detect when it is within three symbols of the end of the string it is processing.  So, the design of an FSA for this task must treat any substring 101 that it encouunters in the binary string as possibly being at the end of the entire binary input string, and if another symbol appears afterwards to make provisions for this.

An NFSA for this problem is much easier to design.  It appears in the applet below.