Ein Nondeterministic Finite Automaton (NFA), der die oben genannte Sprache akzeptiert, könnte wie folgt aussehen:
- Es gibt drei Zustände: q0, q1, q2, die für die Überprüfung der jeweils ersten, zweiten und dritten Stelle der Eingabe verwendet werden.
- Der Anfangszustand ist q0.
- Der Endzustand ist q2.
- Es gibt Übergänge von q0 nach q0, q1 und q2 bei Eingabe von 0 oder 1.
- Es gibt Übergänge von q1 nach q1, q2 bei Eingabe von 0 oder 1.
- Es gibt Übergänge von q2 nach q2 bei Eingabe von 0 oder 1.
So akzeptiert der NFA jede Eingabe die enthält 000 oder 111, da er sich bei der Eingabe der dritten Null oder eins im Zustand q2 befindet, und dieser Zustand ist ein Endzustand.