06 — אי־דטרמיניזם בלי מעברי אפסילון

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

הקודם · מפת הקורס · הבא

מטרות וידע קודם

נרחיב את DFA של שיעורים 2–5 לאוטומט סופי לא דטרמיניסטי (אסל״ד, NFA), נעקוב אחרי קבוצת מסלולים ונמיר ל־DFA. פונקציית המעברים היא כעת \(\delta:Q\times\Sigma\to\mathcal P(Q)\): לכל מצב וסימן מקבלים קבוצת יעדים, שיכולה להיות גם ריקה.

כל חץ חישובי צורך סימן אחד. אין מעברי אפסילון, לרבות חצים “לבחירת מסלול” בתחילת ההרצה או בסופה. המילה מתקבלת אם קיים לפחות מסלול אחד שצרך את כולה וסיים במצב מקבל. מסלול שנכשל אינו פוסל מסלול אחר.

דוגמה פתורה 1 — סיומת bbc

מטלה 2 שאלה 2א, מעל \(\{a,b,c\}\). q0 קורא קידומת שרירותית. על b אפשר גם להישאר בו וגם להתחיל לבדוק שזו תחילת הסיומת המבוקשת. התחלה q0, \(F=\{q3\}\).

stateDiagram-v2
    direction LR
    state " " as start
    start --> q0
    q0 --> q0: a,b,c
    q0 --> q1: b
    q1 --> q2: b
    q2 --> q3: c
    class q3 accepting
    class start invisible
    classDef accepting stroke:#000,stroke-width:4px
    classDef invisible fill:transparent,stroke:transparent

אם התרשים רחב מהמסך, אפשר לגלול אותו אופקית; במקלדת התמקדו בתרשים והשתמשו בחצים.

המסגרת העבה מסמנת מצב מקבל; חץ ההתחלה אינו צעד. המעברים שאינם מצוירים אינם קיימים. בענף שעובר מ־q0 ל־q1 כבר נקרא ה־b הראשון של הסיומת, ולכן נשאר לקרוא רק bc.

יש מצב מקבל בקבוצה האחרונה ולכן המילה מתקבלת. על bbbca מגיעים אחרי c לאותה קבוצה, אבל ה־a הבא משאיר רק {q0}: זו דחייה. אין להוסיף לולאה ל־q3, כי היא תהפוך את הדרישה “מסתיימת” ל־”מכילה”.

דוגמה פתורה 2 — המרה מלאה ל־DFA

כל קבוצת מצבים אפשריים תהפוך למצב יחיד של DFA. מתחילים ב־\(\{q0\}\); על סימן \(x\) מחשבים \(\bigcup_{q\in S}\delta(q,x)\). מצב קבוצה מקבל אם הוא מכיל מצב מקבל של ה־NFA.

בדוגמה שלנו יש רק ארבע קבוצות נגישות: A={q0}, B={q0,q1}, C={q0,q1,q2}, D={q0,q3}.

התחלה A, ורק D מקבל. זו טבלה דטרמיניסטית מלאה. שתי ההרצות נותנות אותה תשובה לכל מילה, כי מצב ה־DFA הוא בדיוק קבוצת כל היעדים האפשריים של ה־NFA אחרי אותה קידומת. בבנייה כללית עשויה להופיע הקבוצה הריקה; היא מצב מלכודת, לא המילה הריקה.

יישום נוסף — מכילה aaa או aba ומסתיימת ב־b

למטלה 2 שאלה 2ב אפשר להשתמש ב־s עם לולאה על כל האלפבית, ובנוסף s --a--> p. מכאן p --a--> r, p --b--> t, ואז גם r --a--> u וגם t --a--> u. כך גילינו אחת משתי התבניות. מ־u ומ־v, על b עוברים ל־v, ועל a,c ל־u; רק v מקבל. התחלה s. כל החצים צורכים סימן, ובחירת התבנית נעשית על אות קלט אמיתית.

טעויות נפוצות

• NFA אינו מכונה ש”בוחרת תמיד נכון” בהרצה פיזית; זוהי הגדרת קבלה באמצעות קיום מסלול.
• כדי להוכיח דחייה צריך שכל המסלולים ייכשלו. מעקב קבוצות מונע שכחת ענף.
• המרה אינה מוסיפה כוח חישובי: NFA ו־DFA מקבלים בדיוק את השפות הרגולריות. NFA עשוי להיות נוח או קטן יותר.

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

תרגול

1. מעקב קבוצות

הריצו abbbc ו־bbcc בדוגמה 1.

2. חפיפה בין תחילית לתבנית

במטלה 2 שאלה 2ג נדרשות תחילית ab, הופעת abb, וסיומת ab או bb. מדוע מסוכן להתחיל לחפש abb רק אחרי שהתחילית הסתיימה?

3. שני קשיים והוראה מתקנת

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

הקודם · מפת הקורס · הבא