אוטומט סופי לא דטרמיניסטי

מתוך ויקיפדיה, האנציקלופדיה החופשית

אוטומט סופי לא דטרמיניסטי הוא הכללה של אוטומט סופי דטרמיניסטי המאפשרת לאוטומט לבחור במספר דרכי פעולה אפשריות עבור קלט נתון בניגוד לדרך הפעולה היחידה אליה מחוייב אוטומט דטרמיניסטי.

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

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

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

[עריכה] מהות אי הדטרמיניזם

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

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

[עריכה] הגדרה פורמלית

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

A=\left\{\Sigma, Q, Q_0, F, \delta\right\}

כאשר:

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

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

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

שפות אחרות