אוטומטים ושפות פורמליות/אוטומט סופי לא דטרמיניסטי: הבדלים בין גרסאות בדף

ישנן שלוש דרכים עיקריות להבין את היכולות האי דטרמיניסטיות של האוטומט הלא דטרמיניסטי.

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

#אפשרות שלישית היא לראות את האוטומט כאילו הוא בודק באופן דטרמיניסטי את כל המסלולים האפשריים בהינתן מילת קלט מסוימת, ואם אחד מהמסלולים מקבל אותה, האוטומט כולו מקבל אותה.