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

בפתיחה יש דוגמה פשוטה: כשהאוטומט נמצא ב-Q1 וקלט הוא הספרה 1, הוא יכול לבחור לעבור ל-Q2 או ל-Q4. אותו הדבר לגבי הספרה 0 במצבים אחרים. בגלל שאינו מתייחס לכל אות בכל מצב (מלבד Q0), הוא עלול להיתקע, כלומר, להגיע למצב שבו אין מעבר אפשרי והמילה לא מתקבלת. מילה כמו 10 תתקבל רק אם קיים מסלול חישוב שמסתיים במצב מקבל.

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

האוטומט הלא דטרמיניסטי מתרחב על הדטרמיניסטי בשלוש דרכים עיקריות:
- עבור כל מצב ואות קלט, ניתן לעבור למספר מצבים ולא רק למצב יחיד.
- נוסף האפשרות של "מעבר ε", מעבר בין מצבים בלי לקרוא אות קלט.
- ניתן לבחור מתוך מספר מצבים התחלתיים.

אי־דטרמיניזם אפשרי להתפשט בשלושה רעיונות עיקריים: ניתן לדמיין שהאוטומט "מנחש" את המעבר הטוב ביותר בזמן הקריאה; ניתן לראות אותו כמתקיים חישוב מקבילי שבו הוא מתפצל לכל אפשרות; או כאילו הוא בודק בדטרמיניסטיות את כל המסלולים האפשריים, ואם אחד מהם מקבל את המילה, גם האוטומט מקבל אותה.

אוטומט סופי לא דטרמיניסטי מוגדר כחמישייה (Σ, Q, q0, F, δ). השפה שהוא מזהה היא קבוצת המילים שקיימת להן דרך (מסלול חישוב) שמסתיימת במצב מקבל. ההרחבה הטבעית של פונקציית המעברים, שמטפלת במילים ובקבוצות מצבים, מסמנת אם ניתן להגיע למצבים מקבלים מתוך מצב התחלתי באמצעות המילה הנתונה.

האוטומט הלא דטרמיניסטי שקול לאוטומט הדטרמיניסטי: כל שפה שניתנת לקבלה על ידי אחד מהם ניתנת גם לקבלה על ידי השני. בכיוון מהדטרמיניסטי ללא־דטרמיניסטי זה ברור. בכיוון ההפוך בונים אוטומט דטרמיניסטי שבו כל "מצב" הוא בעצם קבוצה של מצבים של האוטומט המקורי. פונקציית המעברים מפנה מקבוצה של מצבים לקבוצת כל המצבים שניתן להגיע אליהם בעזרת תו נתון. מצב יחשב מקבל אם לפחות אחד מהמצבים שבקבוצה הוא מקבל. הבנייה הזאת מייצרת אוטומט שקול, אך מספר המצבים בו גדל באופן מעריכי ביחס למקור (אם ב-NFA היו n מצבים, ב-DFA שהתקבל יהיו בערך 2^n מצבים). לכן פעמים רבות קל יותר לתכנן NFA אף על פי שבסוף אפשר להמירו ל-DFA. ההוכחה לשקילות היא קונסטרוקטיבית בשני הכיוונים.

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

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

האוטומט שונה מהרגיל בשלוש דרכים עיקריות:
- הוא יכול לעבור למספר מצבים עבור אות אחת.
- יש לו אפשרות לעבור בלי לקרוא אות (מעבר בלי אות, קרוי "ε").
- הוא יכול להתחיל ממספר מצבים שונים.

אפשר לדמיין את זה כך: האוטומט "מנחש" את המעבר הטוב, או שהוא מתפצל ורץ על כמה דרכים יחד. די שאחת מהדרכים תסתיים במצב מקבל והסיפור מסתיים בטוב.

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