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

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

 

ראה את האסל"ד הבא, המוגדר מעל האלפבית הבינארי:

 

 

נתאר את החישוב עבור הקלט "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.)

נבצע את האמור לעיל נקבל את האסל"ד השקול

 

שים לב למצב <math>\emptyset</math>. האס"ד יגיע אליו אם היה במצב {4} וכעת נקרא התו "1". ואכן, אם באסל"ד המקורי ההינו במצב 4 (אך ורק במצב 4), אם נקרא "1" בקלט המכונה מסתיימת בכשלון. מצב כשלון זה מתואר על ידי הבור <math>\emptyset</math> שניתן להכנס אליו, אבל לא ניתן לצאת ממנו. כמו כן כל המצבים באוטומט הדטרמיניסטי (פרט לבור) הם מצבים מקבלים, מכיוון שהם מכילים את המצב 3 או את המצב 4 שהם מצבים מקבלים במכונה המקורית.

 

{{תרגיל

|שאלה=נתון האסל"ד הבא מעל <math>\Sigma=\{a,b\}</math>.

|פתרון=האוטומט הסופי הדטרמיניסטי השקול נתון על-ידי