אוטומטים ושפות פורמליות/אוטומט סופי לא דטרמיניסטי

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

במכונה זו ייתכן שלכל מצב יש מספר מעברים שניתן לעבור אליהם בקריאת קלט, כלומר פונקציית המעברים מוגדרת מכל מצב ואות בקלט אל סט של מצבים.

מהות אי הדטרמיניזם

ישנן שלוש דרכים עיקריות להבין את היכולות האי דטרמיניסטיות של האוטומט הלא דטרמיניסטי.

1. ניתן לחשוב על האוטומט כאילו הוא "מנחש" בזמן קריאה של מילה מהו המעבר הטוב ביותר עבורו, שיבטיח כי אם המילה בשפה, הוא יקבל אותה. ניתן לראות זאת גם כאילו הוא "מגריל" את המעבר שבו הוא יבחר, כאשר ההגרלה מתבצעת באמצעות "מטבע קסם" שתמיד נותן את הבחירה האופטימלית.
2. ניתן גם לחשוב על האוטומט כאילו הוא מבצע חישוב מקבילי: בכל פעם שהוא מגיע להתפצלות שבה ניתן עבור אות מסוימת ללכת למספר מצבים, הוא מתפצל למספר אוטומטים שכל אחד מהם בודק את אחת מהאפשרויות, ודי שאחד מהם יקבל את המילה.
3. אפשרות שלישית היא לראות את האוטומט כאילו הוא בודק באופן דטרמיניסטי את כל המסלולים האפשריים בהינתן מילת קלט מסוימת, ואם אחד מהמסלולים מקבל אותה, האוטומט כולו מקבל אותה.

הגדרה פורמלית

אוטומט סופי לא דטרמיניסטי (אסל"ד) $\ A$ מוגדר באמצעות -

$A=(\Sigma ,Q,q_{0},F,\delta )$

כאשר:

• $\ \Sigma$ היא א"ב הקלט
• $\ Q$ היא קבוצה סופית של מצבים
• $\ q_{0}$ המצב ההתחלתי של האוטומט (ממנו מתחיל החישוב), $\ q_{0}\in Q$
• $\ F$ היא קבוצת מצבים מקבלים, $\ F\subseteq Q$. מצב מקבל הוא מצב שסיום החישוב בו מסמן שהמילה התקבלה
• $\ \delta$ היא פונקציית המעברים,

$\ \delta :Q\times (\Sigma \cup \left\{\varepsilon \right\})\rightarrow P(Q)$ (לכל מצב ואות קלט או המילה הריקה מותאמת קבוצה של מצבים שאליהם יכול האוטומט לעבור)

השפה שאותה מקבל האוטומט מוגדרת כאוסף המילים עבורן קיים מסלול חישוב של האוטומט שמסתיים במצב מקבל. בניסוח פורמלי, $\ L(A)=\left\{w\in \Sigma ^{*}|\delta (q_{0},w)\cap F\neq \emptyset \right\}$, כאשר כאן $\ \delta$ היא ההרחבה הטבעית של פונקציית המעברים עבור מילים וקבוצות של מצבים - כלומר קבוצת כלל המצבים מהם ניתן להגיע אם מתחילים במצב $q_{0}$ וקוראים את הקלט $w$.

שקילות לאוטומט דטרמיניסטי

ניתן להפוך כל אסל"ד לאס"ד, על-ידי מעקב פשוט על קבוצת כל המצבים שאליהם האסל"ד יכול להגיע. בהנתן אסל"ד $N=(Q,\Sigma ,q_{0},F_{N},\delta _{N})$ נבנה אס"ד $D=(S,\Sigma ,s_{0},F_{D},\delta _{D})$ באופן הבא:

• כל מצב של $D$ יהיה קבוצה של מצבים מ-$N$, כלומר $S=P(Q)=2^{Q}$
• המצב ההתחלתי - צריך להיות שקול ל-$q_{0}$ אבל נזכור שכל מצב ב-$S$ הוא קבוצה של מצבי $Q$, לכן $s_{0}=\{q_{0}\}$.
• האלפבית זהה
• על מנת להבין את פונקציית המעברים של האס"ד, נחזור לאינטואיציה -
  • מכל מצב ב-$Q$ שהאסל"ד יכול להיות בו, אנחנו עוברים לקבוצה של מצבים הנתונים על-ידי $\delta _{N}$. לכן בצורה דומה האס"ד יעבור מקבוצת מצבי ה"מקור" לקבוצה המכילה את כל המצבים שהאסל"ד יכול להגיע, אם נקראה האות המסויימת.
  • נוסף על כך צריך להתייחס למעברי אפסילון. ייתכן שהאסל"ד עובר למצב, שממנו יש חיצי אפסילון למצבים רבים. המשמעות הוא שהאס"ד למעשה צריך להיות בכלל המצבים הללו גם כן..
  • באופן פורמלי

$\delta (s\in S,a\in \Sigma )=\bigcup _{q\in Eclosure[s]}Eclosure[\delta _{N}(q,a)]$

כאשר $Eclosure[W]$ (נקרא סְגוֹר-אפסילון) מייצג את קבוצת כל המצבים אליהם ניתן להגיע על-ידי מעברי אפסילון בלבד מתוך המצבים שבקבוצה $W$. הסגור מכיל גם המצבים שבקבוצה W עצמה.

• מצבים מקבלים - מספיק שהאסל"ד הגיע למצב מקבל אחד על מנת שהקלט ייתקבל, לכן באס"ד נקבע כמצבים מקבלים את כל קבוצות המצבים שמכילות לפחות מצב אחד מתוך $F_{N}$. כלומר, אם האסל"ד היה יכול לסיים במצב שהוא מקבל, המצב באס"ד שמתאר את קבוצת המצבים של האסל"ד יהיה מקבל.

דוגמא

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

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

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

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

תרגיל

הפכו את האוטומט הבא לאוטומט דטרמיניסטי:

פתרון

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

הפרק הקודם: אוטומט סופי דטרמיניסטי

אוטומט סופי לא דטרמיניסטי תרגילים

הפרק הבא: תכונות של שפות רגולריות