בשיעור זה נלמד לפשט הגדרות, להפריד בין פרמטרים תלויים לבלתי תלויים, לבדוק הכלה באמצעות הוכחה או דוגמה נגדית, ולזהות חיתוכים פשוטים שמסתתרים בין שפות מסובכות. התרגול נשען על מטלות 3–4.
מטרות וידע קודם
נשתמש בסגירות ובהוכחות אי־רגולריות משיעורים 7–8. להוכחת הכלה \(A\subseteq B\) נבחר מילה שרירותית ב־\(A\) ונראה שהיא ב־\(B\). להפרכה מספיק למצוא מילה אחת ב־\(A\setminus B\). להכלה ממש צריך גם עד ב־\(B\setminus A\).
דוגמה פתורה 1 — אילוץ שנעלם כשמסתכלים על המילים
מטלה 4 שאלה 4 כוללת \(L_1=\{(ab)^n(ab)^m\mid n\ge m\ge0\}\). כל מילה כזאת היא \((ab)^{n+m}\), ולכן \(L_1\subseteq\{ab\}^*\). בכיוון השני, לכל \((ab)^t\) נבחר \(n=t,m=0\); האילוץ מתקיים. לכן \(L_1=\{ab\}^*\) וזו שפה רגולרית.
כדי להוכיח ששתי הגדרות מתארות אותה שפה, הראו שני כיוונים. כאן הבחירה \(m=0\) מוכיחה שכל מספר חזרות אפשרי, למרות אי־השוויון בנוסח המקורי.
דוגמה פתורה 2 — חיתוך עם משלים במטלה 3
בשאלה 2 נתונות \(L_2=\{(ac)^kb^k\mid k\ge0,\ k\bmod2=0\}\) ו־\(L_3\), שפת המילים המכילות \((ac)^k\) עבור איזשהו \(k>1\). התנאי האחרון שקול להופעת acac: אם יש רצף ארוך יותר, תחילתו מכילה acac, ולהפך אפשר לבחור \(k=2\).
במקור \(L_7=\overline{L_3}\cap L_2\) — הקו מעל \(L_3\) חשוב. עבור \(k=0\) נקבל ε, שאינה מכילה acac. לכל \(k\) זוגי וחיובי מתקיים \(k\ge2\), ולכן המילה כן מכילה acac. מכאן \(L_7=\{\varepsilon\}\), שפה סופית ורגולרית.
כעת נבדוק שתי טענות מאותה שאלה. \(L_2\subset L_3\) שקרית בגלל ε. אם \(L_4\) אינה מכילה ac ומכילה רצף \(b^k\) עבור איזשהו \(k>1\), אז \(L_3\cap L_4=\varnothing\): הופעת acac מחייבת הופעת ac. הדרישה הנוספת ל־bb ב־\(L_4\) אינה יכולה לתקן את הסתירה.
דוגמה פתורה 3 — שפות מורכבות, חיתוך זעיר
במטלה 4:
\[L_2=\{a^nb^na^m\mid n\ge m\ge0\},\qquad L_3=\{a^nb^{2n}a^{n\bmod3}\mid n\ge0\}.\]כדי לא לכפות שוויון פרמטרים מראש, נסמן את הפרמטר של \(L_3\) ב־\(r\). עבור מילה לא ריקה בחיתוך, בלוק ה־a הראשון מכריח \(n=r\), ובלוק ה־b מכריח \(n=2r\). מכאן \(n=r=0\), בסתירה לאי־ריקות. ε כן שייכת לשתיהן, ולכן \(L_2\cap L_3=\{\varepsilon\}\).
שמות משתנים מקומיים להגדרת שפה. אין להניח ששני משתנים בשם \(n\) בשתי שפות הם אותו מספר לפני שמשווים את המילה עצמה. בנוסף, בתנאי המקור של \(L_3\) מופיע גם \(m\) שאינו משתתף בביטוי; הוא מיותר ואינו משנה את קבוצת המילים.
נבדוק גם \(L_4=\{w\mid\#_a(w)>\#_b(w)\}\). הטענה \(L_2\subset L_4\) שקרית: ab ב־\(L_2\) עם \(m=0\) ובעלת כמויות שוות. ב־\(L_3\), ההפרש הוא \((n\bmod3)-n\le0\), ולכן \(L_3\cap L_4=\varnothing\). לעומת זאת \(\overline{L_4}\cap L_1\) אינו ריק: הוא כל \(L_1\), כי ב־\((ab)^t\) הכמויות שוות.
מפרידים מקור, פרשנות ופתרון
במטלה 5 שאלה 2 הדוגמאות החיוביות אינן מתאימות להסבר על מיקום c. בשיעור 11 נבחר במפורש את ההגדרה המילולית: c מפריד לפני הבלוק האחרון, ויתר המפרידים הם b. לא נתאים אוטומט לשתי הגדרות סותרות. זיהוי אי־התאמה הוא חלק מהפתרון, ולא תקלה שצריך להסתיר.
תרגול
1. שרשור עם חיתוך ריק?
במטלה 3 שאלה 2, \(L_1=\{a^2c^{2+k}b^k\mid k\ge0,\ k\bmod2=0\}\). האם \((L_1\cap L_2)L_5=\varnothing\), כאשר \(L_2\) היא מדוגמה 2 ו־\(L_5\) היא השפה במטלה?
רמז ופתרון
רמז: השוו את שני הסימנים הראשונים, ובדקו בנפרד ε. פתרון: כל מילה ב־\(L_1\) מתחילה aa. כל מילה לא ריקה ב־\(L_2\) מתחילה ac; ε אינה ב־\(L_1\). לכן החיתוך ריק, ושרשורו עם כל שפה ריק. אין צורך לנתח את \(L_5\) כדי לענות.
2. רגולריות אינה נקבעת לפי המראה
האם \(\{a^n b^m\mid n,m\ge0\}\) רגולרית? השוו ל־\(\{a^n b^n\mid n\ge0\}\).
רמז ופתרון
רמז: האם אחרי סיום בלוק ה־a צריך לזכור את אורכו המדויק? פתרון: הראשונה היא \(\{a\}^*\{b\}^*\) ולכן רגולרית; מספיק לזכור את שלב הקריאה. בשנייה יש להשוות כמויות, והוכחנו בשיעור 8 שאינה רגולרית. אותה צורת בלוקים אינה מבטיחה אותו סיווג.
3. השלמת תרשים קבוע
מטלה 2 שאלה 4 דורשת שלא להתחיל ב־ab, להכיל לפחות אחד מהרצפים aa,bb, ולא להכיל את שניהם. השלימו את התרשים שבמקור בלי להוסיף מצבים.
רמז ופתרון
רמז: אחרי הבחירה איזה זוג כבר הופיע, צריך רק למנוע את הזוג האחר. פתרון: התחלה q0; מקבלים q2,q3,q5,q6. המעברים הבאים הם כולם; תא חסר נשאר לא מוגדר:
| מצב | a |
b |
|---|---|---|
q0 |
q1 |
q4 |
q1 |
q2 |
— |
q2 |
q2 |
q3 |
q3 |
q2 |
— |
q4 |
q7 |
q5 |
q5 |
q6 |
q5 |
q6 |
— | q5 |
q7 |
q2 |
q4 |
q4,q7 זוכרים שעדיין לא נמצא זוג אחרי התחלה ב־b. q2,q3 זוכרים שנמצא רק aa, ו־q5,q6 שנמצא רק bb. baab מתקבלת, babb מתקבלת, abab נתקעת בתחילית, ו־aabb נתקעת כשמופיע הזוג השני. משמעות המצבים מסבירה גם מדוע אין להוסיף מצב מלכודת כשנדרשה שמירת מספר המצבים.