אוטומטים ושפות פורמליות/אוטומט סופי לא דטרמיניסטי: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
←דוגמא: תיקון טעות לפי משוב |
||
שורה 44:
<center>[[קובץ:NFA-powerset-construction-example.svg]]</center>
נתאר את החישוב עבור הקלט "11". בתחילה, המכונה במצב 1, אבל עקב מעברי-אפסילון היא יכולה להיות באחד מהמצבים {1,2,3}. אחרי עיבוד האות הראשונה (1), המכונה יכולה להמצא במצבים {2,4}: אם היתה במצב 1 או 3, המכונה בבעיה (לא מוגדר מעבר עבור קלט 1), וענף החישוב הנ"ל חסר משמעות; אם היתה במצב 2 היא יכולה לעבור למצב 2 או למצב 4. כעת מעובדת אות הקלט השניה (1). אם המכונה היתה ב-2 כעת היא תהיה ב2 או ב4. אם הייתה ב-4,
נבצע את האמור לעיל נקבל את האס"ד השקול
|