אוטומט סופי לא דטרמיניסטי

יש מכונה שקוראים לה אוטומט. אוטומט זה יכול לבחור כמה דרכים שונות להגיב על אות קלט. לפעמים הוא ידע לאן ללכת, ולפעמים לא, ואז הוא נעצר והמילה לא מתקבלת. '''אוטומט סופי לא דטרמיניסטי''' זה אוטומט שמותר לו לבחור בין כמה מעברים. זה הוצג על ידי רבין וסקוט ב-1959. האוטומט שונה מהרגיל בשלוש דרכים עיקריות...