Nichtdeterministische Endliche Automaten

Manchmal sind gewisse Problemstellungen zu komplex, um sie direkt als DFA zu entwerfen. Der nichtdeterministische (also uneindeutige) endliche Automat kann für solche Aufgaben besser geeignet sein. Im Unterschied zum DFA ist beim NFA folgendes möglich:

• Von einem Zustand kann es mehrere Möglichkeiten je Eingabe geben (siehe q2 - 2x 1 möglich)
• Eingaben können bei einem Zustand auch gar nicht vorkommen (siehe q2 - keine 0)

Ausschlaggebend ist, dass ein Weg existiert, welcher das Wort akzeptiert.