הצגת המקור של הדף "אוטומט סופי לא דטרמיניסטי"

[[קובץ:Nondeterministic finite state machine.jpg|ממוזער|שמאל|350px| האוטומט הנוכחי הוא אוטומט סופי לא דטרמיניסטי (אסל"ד). אם אנו נמצאים ב[[מצב (מדעי המחשב)|מצב]] <math>Q_1</math> ומגיעה הספרה 1 האוטומט יכול לעבור למצב <math>Q_2</math> או למצב <math>Q_4</math>. אותו הדבר לגבי קליטת הספרה 0 - האוטומט יכול לבחור לעבור או למצב <math>Q_6</math> או למצב <math>Q_8</math>. עצם כך שהאוטומט הוא אוטומט סופי לא מלא (אסל"מ) נובעת מכך שביתר המצבים, מלבד המצב ההתחלתי <math>Q_0</math>, אין התייחסות לכל אות קלט מא"ב האוטומט. לפיכך, אם נמצאים במצב <math>Q_2</math> ומגיעה הספרה 0 האוטומט "לא יודע" לאין ללכת והוא נתקע. ההיתקעות משמעה שהמילה (הקלט) לא מתקבלת על ידי האוטומט. אותה מילה (10) הייתה מתקבלת לו היה קיים מסלול חישוב כלשהו שסיומו היה מוביל למצב מקבל]]

'''אוטומט סופי לא דטרמיניסטי''' הוא [[מודל מתמטי]] המהווה [[הכללה (מתמטיקה)|הכללה]] של [[אוטומט סופי דטרמיניסטי]]{{הערה|ההכללה המדוברת, איננה [[הכללה (מתמטיקה)|הכללה מתמטית]] במובנה הרגיל, אלא הכללה רק מבחינה טכנית (כתיבה) ופילוסופית (זווית ראייה / הסתכלות), באפשרויות הנוספות: לאפיין, לייצג ולחשב אוטומט. אוטומט סופי לא דטרמיניסטי (אסל"ד) [[שקילות (מתמטיקה)|שקול]] לחלוטין לאוטומט סופי דטרמיניסטי (אס"ד) (מבחינת [[חישוביות|כוח ויכולת החישוב]])!}} בכך שהוא מאפשר בחירה בין מספר דרכי פעולה עבור קלט נתון, בניגוד לדרך הפעולה היחידה שלפיה פועל אוטומט דטרמיניסטי.
המודל הוצג לראשונה על ידי [[מיכאל רבין]] ו[[דנה סקוט]] במאמר מ-[[1959]].

ההכללה של האוטומט הסופי הדטרמיניסטי מתבטאת בשלוש הרחבות עיקריות:
# עבור כל [[מצב (מדעי המחשב)|מצב]] של האוטומט ואות קלט נתונה, האוטומט הלא דטרמיניסטי יכול לעבור למספר מצבים, ולא למצב יחיד כמו שעובר האוטומט הדטרמיניסטי.
# לאוטומט מוספת האפשרות של "מסע <math>\varepsilon</math>" - מעבר ממצב אחד למשנהו מבלי שהוא יקלוט אות קלט כלשהי.
# לאוטומט מוספת האפשרות לבחור בין מספר מצבים התחלתיים.

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

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

==הגדרה פורמלית==
{{סימון מתמטי}}
אוטומט סופי לא דטרמיניסטי <math>\ A</math> [[הגדרה (מתמטיקה)|מוגדר]] באמצעות ה[[N-יה סדורה|חמישייה הסדורה]] הבאה:

<math>A=\left(\Sigma, Q, q_0, F, \delta\right)</math>

כאשר:
*<math>\Sigma</math> היא (קבוצת) [[אלפבית (שפה פורמלית)|אלפבית]] הקלט. כל [[איבר (מתמטיקה)|איבר]] בקבוצה זו מכונה "אות".
*<math>Q</math> היא קבוצה סופית של מצבים. כל מצב בקבוצה זו הוא, בהכרח, אחד מהשניים: "מצב מקבל" או "מצב לא מקבל".
*<math>q_0 \in Q</math> הוא המצב ההתחלתי של האוטומט (ממנו מתחיל החישוב).
*<math>F \subseteq Q</math> היא קבוצת מצבים מקבלים. מצב מקבל הוא מצב שמסמן שהאוטומט מחזיר תשובה חיובית. כלומר אם בסוף הקלט האוטומט נמצא במצב מקבל, המשמעות היא שהקלט הוא מילה בשפה של האוטומט.
*<math>\delta \colon Q\times \Sigma\cup\left\{\varepsilon\right\} \to \mathcal{P}(Q)</math> היא [[פונקציית מעברים|פונקציית המעברים]]: לכל מצב ואות קלט או הסימן <math>\varepsilon</math>{{הערה|אין לבלבלו עם המילה הריקה - האוטומט לא קורא אותה, אלא יכול לעבור לקבוצת מצבים מסוימת ללא קריאת מילת קלט. מעבר שכזה מכונה "מסע-<math>\varepsilon</math>". ניתן להגדיר מודל שקול בו לא מתירים מסעי-<math>\varepsilon</math>: מכל אוטומט ניתן לבנות אוטומט שקול באמצעות סילוק המסעי-<math>\varepsilon</math>}} [[יחס (תורת הקבוצות)|מותאמת]] קבוצה של מצבים, שאליהם יכול האוטומט לעבור. כלומר, לא מותאם (בהכרח) רק מצב אחד ויחיד – וזו הסיבה העיקרית שבגינה אוטומט זה אינו נחשב [[דטרמיניזם|דטרמיניסטי]].

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

נעיר, שמודל זה שקול למודל בו יש קבוצה <math>Q_0 \subseteq Q</math> של מספר מצבים התחלתיים שונים.

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

כדי להוכיח שקילות בכיוון ההפוך, בהינתן אוטומט לא-דטרמיניסטי, בונים אוטומט שקבוצת המצבים שלו היא [[קבוצת החזקה]] של קבוצת המצבים של האוטומט המקורי. פונקציה תוביל מקבוצת מצבים, בהינתן תו, לקבוצת כל המצבים שניתן להגיע אליהם בעזרת התו מהקבוצה שהיינו בה. המצב ההתחלתי יהיה קבוצת המצבים ההתחלתיים, ומצב יהיה מקבל אם לפחות אחד מהמצבים שבקבוצה הוא מקבל. קיבלנו אוטומט שקול, אך מספר המצבים בו גדול באופן [[אקספוננט|אקספוננציאלי]] מזה של האוטומט המקורי (אם באוטומט הלא דטרמיניסטי היו <math>n</math> מצבים אז באוטומט הדטרמיניסטי שבנינו בהוכחה יהיו <math>2^n</math> מצבים). על כן האוטומט הלא דטרמיניסטי מקל פעמים רבות על הבנייה והיישום של מודל לזיהוי שפה רגולרית מסוימת.

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

==ראו גם==
{{מיזמים|ויקיספר=אוטומטים ושפות פורמליות}}
* [[מכונת טיורינג לא-דטרמיניסטית]]

{{-}}

== לקריאה נוספת ==
* {{פא"ר|מספר=418|שם הספר=אוטומטים ושפות פורמליות א|כותב=שמואל זקס ו[[נסים פרנסיז]]|שנה=2000}}
* {{פא"ר|מספר=419|שם הספר=אוטומטים ושפות פורמליות ב|כותב=שמואל זקס ו[[נסים פרנסיז]]|שנה=2000}}

== קישורים חיצוניים ==

* [https://gadial.net/2014/11/19/nondeterministic_automata/ אוטומטים אי דטרמיניסטיים ושאר מריעין בישין], מתוך הבלוג "לא מדויק" של גדי אלכסנדרוביץ, 19 בנובמבר 2014

==הערות שוליים==
{{הערות שוליים}}

[[קטגוריה:אוטומטים]]

[[nl:Eindigetoestandsautomaat#Niet-deterministische eindige automaten]]