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

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

 

 

<center>[[קובץ:DFA-powerset-construction-example.svg]]</center>