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

נתאר את החישוב עבור הקלט "11". בתחילה, המכונה במצב 1, אבל עקב מעברי-אפסילון היא יכולה להיות באחד מהמצבים {1,2,3}. אחרי עיבוד האות הראשונה (1), המכונה יכולה להמצא במצבים {2,4}: אם היתה במצב 1 או 3, המכונה בבעיה (לא מוגדר מעבר עבור קלט 1), וענף החישוב הנ"ל חסר משמעות; אם היתה במצב 2 היא יכולה לעבור למצב 2 או למצב 4. כעת מעובדת אות הקלט השניה (1). אם המכונה היתה ב-2 כעת היא תהיה ב2ב-2 או ב4ב-4. אם הייתה ב-4, החישוב ייסתיים וענף זה חסר משמעות. לכן אם המכונה התחילה ב-{2,4} אחרי הקלט השני היא נשארת באחד מהמצבים {2,4}. נשים לב שמצב 4 מצב מקבל, לכן המכונה מקבלת את הקלט "11" (למשל, על ידי מסלול החישוב הבא: מתחילה במצב 1, עוברת עם מעבר אפסילון ל3ל-3 ול2ול-2. כעת קוראת את הקלט הראשון ונשארת במצב 2, וכעת קוראת את הקלט השני ועוברת למצב המקבל 4.).