בשיעור זה נחבר כמה תנאים באותו אוטומט. נזכור זוגיות ושאריות במקום מספרים בלתי חסומים, ונשלב אותן עם תחילית וסיומת בלי לאבד מידע בין הצעדים.
מטרות וידע קודם
אחרי בניית DFA בשיעור 3, נלמד לזכור כמה תנאים יחד. אוטומט אינו יכול לשמור מספר שלם בלתי חסום, אך יכול לשמור את השארית שלו בחלוקה בקבוע. אם יש \(r\) אפשרויות למידע אחד ו־\(s\) לאחר, יש לכל היותר \(rs\) צירופים.
דוגמה פתורה 1 — אורך מתחלק בשלוש ואינה מסתיימת ב־2
מטלה 2 שאלה 1ג, מעל \(\{0,1,2\}\). נשתמש במצב \((r,t)\): השארית \(r\in\{0,1,2\}\), ודגל \(t\) שאומר אם הסימן האחרון היה 2. בהתחלה \((0,N)\); גם למילה הריקה אין סיומת 2, ולכן היא מתקבלת לפי הנוסח הזה.
על כל סימן מעדכנים \(r'=(r+1)\bmod3\). על 2 מעדכנים \(t'=Y\), ועל 0,1 מעדכנים \(t'=N\). רק \((0,N)\) מקבל.
| מצב | 0,1 |
2 |
|---|---|---|
(0,N) |
(1,N) |
(1,Y) |
(0,Y) |
(1,N) |
(1,Y) |
(1,N) |
(2,N) |
(2,Y) |
(1,Y) |
(2,N) |
(2,Y) |
(2,N) |
(0,N) |
(0,Y) |
(2,Y) |
(0,N) |
(0,Y) |
120 עוברת (0,N) → (1,N) → (2,Y) → (0,N) ומתקבלת. 122 מסתיימת ב־(0,Y) ונדחית. 10 מסתיימת ב־(2,N) ונדחית. לכל רכיב תפקיד עצמאי: אף בדיקה אינה מחליפה את האחרת.
דוגמה פתורה 2 — מתחילה ב־11, מסתיימת ב־1 ואורכה זוגי
למטלה 2 שאלה 1א נפריד את בדיקת שני הסימנים הראשונים. s מצפה ל־1, p מצפה ל־1 השני, וכשל מוביל למלכודת t. אחרי 11 אנו במצב E1: אורך זוגי וסיומת 1.
מכאן ארבעה מצבים: E1,E0,O1,O0. האות E/O מציינת זוגי/אי־זוגי, והספרה 1/0 מציינת האם הסימן האחרון הוא 1 או אינו 1 (כולל 2).
| מצב | 1 |
0,2 |
|---|---|---|
s |
p |
t |
p |
E1 |
t |
E1 |
O1 |
O0 |
E0 |
O1 |
O0 |
O1 |
E1 |
E0 |
O0 |
E1 |
E0 |
t |
t |
t |
התחלה s, \(F=\{E1\}\). 11 מתקבלת; 111 נדחית; 1101 מתקבלת במסלול s → p → E1 → O0 → E1. התחלנו בזוגיות הנכונה אחרי שצרכנו את התחילית, ולא ספרנו אותה שוב.
איך מחברים גם זיהוי תבנית?
בסעיף 1ד נדרשים אורך זוגי, הופעת 12, ואי־סיום ב־22. בונים רכיבים קטנים: דגל “כבר ראיתי 12” עם זיכרון של 1 לפני הגילוי; זוגיות; וסיומת של אפס, אחד או לפחות שני 2 רצופים. בכל צעד מעדכנים את כולם לפי אותו סימן קלט, ומקבלים רק כאשר שלושת התנאים מתקיימים.
זוהי טכניקת מכפלה שננסח בשיעור 7. אין חובה לצייר מראש את כל הצירופים: מתחילים במצב ההתחלתי ומוסיפים רק צירופים שניתן להגיע אליהם. תנאי הזוגיות מופיע פעמיים בנוסח המקור; זה אותו תנאי, לא שתי בדיקות שונות.
אין להסתפק בדוגמה שעובדת: בדקו גם את המילה הריקה, את גבולות התנאים ואת הסימן שיכול לבטל קבלה. האוטומט חייב להתאים להגדרה לכל מילה מעל האלפבית.
טעויות נפוצות
- מונה שאריות מתקדם גם על סימן שלא מעניין רכיב אחר.
- “מסתיימת ב־1” ו־”מכילה 1” מצריכים עדכון שונה: הראשון עשוי להתבטל, השני אינו מתבטל.
- כפל מספר המצבים נותן חסם לבנייה; הוא אינו הוכחה שזה המספר המזערי הדרוש.
כל סימן קלט מעדכן את כל רכיבי הזיכרון יחד. מצב מקבל מסומן רק כשהשארית, השלב והסיומת מקיימים את התנאים בו־זמנית.
תרגול
1. תנאי מיותר במקור
מטלה 2 שאלה 1ב דורשת תחילית 11, הופעת 11, ואורך אי־זוגי. פשטו ובנו טבלת מעברים קצרה.
רמז ופתרון
רמז: התחילית היא בעצמה הופעה. פתרון: מספיק “מתחילה ב־11 ואורכה אי־זוגי”. מ־s על 1 ל־p, ומ־p על 1 ל־E; אחרת למלכודת. מ־E על כל סימן ל־O, ומ־O על כל סימן ל־E. רק O מקבל; המלכודת לולאתית. המילים הקצרות: 110,111,112. אין להוסיף דרישה להופעה שנייה שאינה כתובה.
2. שארית וסדר בלוקים
כיצד בונים אוטומט לשפת מטלה 1 שאלה 3, \(a^n b^m\) עם אורך ששאריתו 1 בחלוקה ב־3?
רמז ופתרון
רמז: זכרו גם אם כבר התחיל בלוק ה־b. פתרון: מצבים (A,r) ו־(B,r) לכל שארית. התחלה (A,0). מ־A על a נשארים בשלב A, ועל b עוברים לשלב B; בכל צעד מוסיפים 1 לשארית מודולו 3. מ־B על b מתקדמים בשארית, ועל a למלכודת. מקבלים (A,1),(B,1). כך baaa נדחית למרות האורך המתאים.
3. בדיקות שמפרידות תנאים
תנו שלוש מילים שמפרות, כל אחת, רק תנאי אחד בדוגמה 2.
רמז ופתרון
רמז: הקפידו ששני התנאים האחרים עדיין נכונים. פתרון: 01 מפרה רק את התחילית; 1100 מפרה רק את הסיומת; 111 מפרה רק את הזוגיות. כל אחת נדחית מסיבה שונה.