בשיעור זה נשתמש בפעולות על שפות כדי לפרק בעיות: חיתוך, איחוד, משלים, הפרש, שרשור, כוכב והיפוך. נבנה מכפלה ונוכיח רגולריות באמצעות סגירות, תוך שמירה על האיסור על מעברי אפסילון.
מטרות וידע קודם
נשתמש בקבוצות וב־DFA/NFA משיעורים 1–6 כדי לבנות שפות חדשות ולהוכיח רגולריות בלי לצייר תמיד אוטומט גדול. סגירות אומרת שפעולה מסוימת על שפות במחלקה משאירה אותנו באותה מחלקה.
| פעולה | פירוש |
|---|---|
| \(A\cup B\) | המילה שייכת לפחות לאחת השפות |
| \(A\cap B\) | המילה שייכת לשתיהן |
| \(\overline A=\Sigma^*\setminus A\) | המילה מעל האלפבית המוסכם ואינה ב־\(A\) |
| \(A\setminus B\) | שייכת ל־\(A\) אך לא ל־\(B\) |
| \(AB\) | אפשר לפצל את המילה ל־\(uv\) עם \(u\in A,v\in B\) |
| \(A^*\) | שרשור של אפס או יותר מילים מ־\(A\) |
| \(A^R\) | היפוך סדר הסימנים בכל מילה של \(A\) |
השפות הרגולריות סגורות לכל הפעולות בטבלה. \(A^*\) מכילה תמיד ε. הסימון \(A^+\) פירושו שרשור של אחת או יותר ממילות \(A\); גם הוא עשוי להכיל ε אם ε עצמה ב־\(A\).
דוגמה פתורה 1 — מכפלה לחיתוך
מעל \(\{a,b\}\) נרצה אורך זוגי וסיומת a. רכיב אחד זוכר E/O, ואחר זוכר A/N — האם הסימן האחרון הוא a. התחלה EN, ורק EA מקבל.
| מצב | a |
b |
|---|---|---|
EN |
OA |
ON |
EA |
OA |
ON |
ON |
EA |
EN |
OA |
EA |
EN |
ba עוברת EN → ON → EA ומתקבלת; ab מסיימת ב־EN ונדחית. באופן כללי מצב המכפלה הוא \((p,q)\), והמעבר הוא \(\delta((p,q),x)=(\delta_A(p,x),\delta_B(q,x))\). לחיתוך שני הרכיבים צריכים להיות מקבלים; לאיחוד די באחד; להפרש הראשון מקבל והשני אינו מקבל. למשלים של DFA משלימים קודם את המעברים ורק אז הופכים קבלה.
דוגמה פתורה 2 — הוכחה באמצעות סגירות בלבד
מטלה 3 שאלה 3 נותנת \(L_1=\{a^n b^k\mid n,k\ge0\}\), \(L_2=\{c^n\mid n\ge0\}\) ו־\(L_3=\{\varepsilon\}\). יש להוכיח רגולריות של:
\[L=\{c^n b^k a^j\mid n>0,\ k,j\ge0\}.\]מסירים מ־\(L_2\) את המילה הריקה, והופכים את המילים של \(L_1\):
\[L=(L_2\setminus L_3)L_1^R.\]הפרש שפות רגולריות רגולרי, היפוך שפה רגולרית רגולרי, וגם השרשור רגולרי. הביטוי מכריח לפחות c אחת, ואחריה אפס או יותר b ואז אפס או יותר a. זו גם בדיקת שוויון השפות, לא רק ציטוט רשימת תכונות.
סגירות מחייבת לבדוק את ההנחות: בפעולות הבוליאניות האוטומטים פועלים מעל אותו אלפבית, ולפני משלים צריך DFA מלא. אין להפוך מצבים מקבלים של NFA ולצפות לקבל משלים.
בונים שרשור וכוכב בלי אפסילון
אפשר להוכיח סגירות בלי להציג בנייה אסורה. הנה בנייה ישירה: עבור \(AB\), קחו עותקים זרים של האוטומטים ומצב התחלה חדש s. ממנו, על סימן \(x\), העתיקו את יעדי מצב ההתחלה של \(A\), וגם את יעדי התחלת \(B\) אם \(\varepsilon\in A\). מכל מצב מקבל של \(A\), על \(x\), הוסיפו אפשרות להגיע ליעדים שאליהם התחלת \(B\) מגיעה על \(x\). המעבר הזה כבר קורא את הסימן הראשון של החלק השני.
המצבים המקבלים הם מקבלי \(B\), וגם מקבלי \(A\) אם \(\varepsilon\in B\). s מקבל בדיוק אם שתי השפות מכילות ε. יתר המעברים הפנימיים נשארים. כך אין צורך בחץ ללא קלט בגבול בין שני חלקי המילה.
ל־\(A^*\) מוסיפים התחלה חדשה מקבלת, שמחקה על כל סימן את מעברי ההתחלה הישנה. מכל מקבל של \(A\) מוסיפים על כל סימן גם את יעדי ההתחלה הישנה, כדי להתחיל מילה נוספת. שומרים את המקבלים הישנים. s אינו יעד של מעברים: קבלתו מוסיפה רק את המילה הריקה.
בהיפוך \(A^R\) הופכים את כיוון כל החצים ומשאירים את הסימנים. מוסיפים התחלה חדשה שמעתיקה, על כל סימן, את יעדי כל המצבים שהיו מקבלים באוטומט המקורי לאחר ההיפוך. המצב ההתחלתי המקורי הוא המקבל החדש; ההתחלה החדשה מקבלת גם היא אם המקור קיבל ε. זו דרך לאחד התחלות אפשריות בלי אפסילון.
יישום למטלה 2 שאלה 3
“לא מכילה aa, לא מכילה aba, ומסתיימת ב־a” הוא חיתוך של שלוש שפות רגולריות. בבודק האיסורים מספיק לזכור את הסיומת המועילה ε, a או ab, ומלכודת אם נמצא איסור. מעל \(\{a,b,c\}\):
| מצב | a |
b |
c |
|---|---|---|---|
s |
a1 |
s |
s |
a1 |
t |
ab1 |
s |
ab1 |
t |
s |
s |
t |
t |
t |
t |
התחלה s; רק a1 מקבל, וכך מקיימים גם את הסיומת. אפשר להגיע לבנייה הקומפקטית הזאת מתוך מכפלה ולזהות איזה מידע באמת נחוץ.
בהוכחת סגירות מציינים גם את הפעולה וגם מדוע הביטוי מתאר בדיוק את השפה המבוקשת. תכונת סגירות לבדה אינה מתקנת פירוק שגוי של השפה.
תרגול וטעויות נפוצות
1. שרשור אינו חיתוך
חשבו \(AB\) ו־\(A\cap B\) עבור \(A=\{a,ab\}\), \(B=\{b,\varepsilon\}\).
רמז ופתרון
רמז: בשרשור בוחרים מילה מכל קבוצה. פתרון: \(AB=\{ab,a,abb\}\); המילה ab מופקת בשתי דרכים אך נכתבת פעם אחת בקבוצה. החיתוך ריק. חיתוך בודק את אותה מילה בשתי שפות; שרשור מפצל אותה.
2. היפוך בלוקים
הפכו את \(\{a^n c^m b^m a^n\mid m>n\ge0\}\).
רמז ופתרון
רמז: ההיפוך משנה את סדר הבלוקים, לא את הקשרים בין המספרים. פתרון: \(\{a^n b^m c^m a^n\mid m>n\ge0\}\). ה־\(a\) נשאר בשני הקצוות משום שהבלוקים הקיצוניים זהים. אין להסיק רגולריות: משפט הסגירות מניח שפת מוצא רגולרית.
3. בודקים את האיסורים
הריצו a, abba, aba, caa בטבלה האחרונה.
רמז ופתרון
רמז: אל תחזרו מהמלכודת אחרי שראיתם איסור. פתרון: a ו־abba מתקבלות. aba מגיעה ל־t בסימן השלישי, ו־caa מגיעה ל־t בסימן השלישי. העובדה ששתיהן מסתיימות ב־a אינה מתקנת איסור קודם.