אוטומטים ושפות פורמליות/אוטומט סופי לא דטרמיניסטי: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שקילות למודל הרגיל |
←דוגמא: תרגיל |
||
שורה 49:
<center>[[תמונה:DFA-powerset-construction-example.svg]]</center>
שים לב למצב <math>\emptyset</math>. האס"ד יגיע אליו אם היה במצב {4} וכעת נקרא התו "1". ואכן, אם באסל"ד המקורי ההינו במצב 4 (אך ורק במצב 4), אם נקרא "1" בקלט המכונה מסתיימת בכשלון. מצב כשלון זה מתואר על ידי הבור <math>\emptyset</math> שניתן להכנס אליו, אבל לא ניתן לצאת ממנו. כמו כן כל המצבים באוטומט הדטרמיניסטי (פרט לבור) הם מצבים מקבלים, מכיוון שהם מכילים את המצב 3 או את המצב 4 שהם מצבים מקבלים במכונה המקורית.
=== תרגיל ===
הפוך את האוטומט הבא לאוטומט דטרמיניסטי
{{תרגיל
|שאלה=נתון האסל"ד הבא מעל <math>\Sigma=\{a,b\}</math>.
[[תמונה:Afn exemple.png]]
|פתרון=האוטומט הסופי הדטרמיניסטי השקול נתון על-ידי
[[תמונה:Afd exemple.png]]}}
| |||