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

אין תקציר עריכה
מ (בוט: מעביר קישורי בינויקי לויקינתונים - d:q617295)
 
השפה שאותה מקבל האוטומט מוגדרת כאוסף המילים עבורן קיים מסלול חישוב של האוטומט שמסתיים במצב מקבל. בניסוח פורמלי, <math>\ L(A)=\left\{w\in\Sigma^*|\delta(Q_0,w)\cap F\ne\emptyset\right\}</math>, כאשר כאן <math>\ \delta</math> היא ההרחבה הטבעית של פונקציית המעברים עבור מילים וקבוצות של מצבים.
 
==שקילות לאוטומט סופי דטרמיניסטי==
האוטומט הסופי הלא דטרמיניסטי שקול לזה הדטרמיניסטי, כלומר כל שפה שניתן לקבל על ידי האחד ניתן לקבל על ידי האחר. שקילות בצד אחד טריוויאלית, כי על כל אוטומט דטרמיניסטי ניתן להסתכל כאוטומט לא דטרמיניסטי (ש"אינו מנצל" את תכונות האי-דטרמיניזם).
 
כדי להוכיח שקילות בכיוון ההפוך, בהינתן אוטומט לא-דטרמיניסטי, בונים אוטומט שקבוצת המצבים שלו היא [[קבוצת החזקה]] של קבוצת המצבים של האוטומט המקורי. פונקציה תוביל מקבוצת מצבים, בהינתן תו, לקבוצת כל המצבים שניתן להגיע אליהם בעזרת התו מהקבוצה שהיינו בה. המצב ההתחלתי יהיה קבוצת המצבים ההתחלתיים, ומצב יהיה מקבל אם לפחות אחד מהמצבים שבקבוצה הוא מקבל. קיבלנו אוטומט שקול, אך מספר המצבים בו גדול באופן [[אקספוננט|אקספוננציאלי]] (אם באוטומט המקורי היו n מצבים בזה יהיו 2<sup>n</sup>) ועל כן האוטומט הלא דטרמיניסטי מקל פעמים רבות על הבנייה והיישום.
 
== לקריאה נוספת ==
8,258

עריכות