מודלים חישוביים — מרחב למידה אישי

ברוכים הבאים ליחידת הלימוד "דקדוקים חסרי הקשר ואוטומטי מחסנית" בקורס "מודלים חישוביים" (20604). יחידה זו מהווה קפיצת מדרגה משמעותית מהמודלים שפגשנו עד כה – האוטומטים הסופיים והשפות הרגולריות. בעוד שאוטומטים סופיים מסוגלים לזהות תבניות פשוטות, הם מוגבלים ביכולתם לטפל במבנים היררכיים ומקוננים, הנפוצים כל כך בשפות תכנות (לדוגמה, התאמת סוגריים או בלוקי קוד מקוננים). יחידה זו מציגה שני מודלים חדשים, דקדוקים חסרי הקשר ואוטומטי מחסנית, המספקים את הכוח החישובי הדרוש לתיאור שפות אלו. הבנה מעמיקה של נושאים אלו חיונית לא רק להצלחה בקורס, אלא גם להבנת עקרונות התכנון של מהדרים (קומפיילרים) ופרשנים (אינטרפרטרים) של שפות תכנות.

מבוא: מעבר לשפות רגולריות

שפות רגולריות, הניתנות לתיאור באמצעות אוטומטים סופיים או ביטויים רגולריים, מוגבלות ביכולתן "לזכור" מידע. הן אינן יכולות לטפל בתלויות ארוכות טווח או במבנים מקוננים שבהם מספר הפתיחות חייב להתאים למספר הסגירות. לדוגמה, השפה של כל המחרוזות מהצורה $a^n b^n$ (כמו $ab, aabb, aaabbb$) אינה רגולרית, מכיוון שאוטומט סופי אינו יכול לספור את מספר ה-a-ים כדי לוודא התאמה למספר ה-b-ים. כדי להתמודד עם אתגרים אלו, אנו זקוקים למודלים חזקים יותר.

שפה חסרת הקשר (Context-Free Language - CFL): שפה שניתן לתאר באמצעות דקדוק חסר הקשר. שפות אלו חזקות יותר משפות רגולריות ומסוגלות לתאר מבנים היררכיים ומקוננים.

דקדוקים חסרי הקשר (CFG): הבסיס התיאורטי

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

דקדוק חסר הקשר (Context-Free Grammar - CFG): רביעייה סדורה $G = (V, \Sigma, R, S)$, כאשר:

$V$: קבוצה סופית של משתנים (או סימנים לא-טרמינליים).
$\Sigma$: קבוצה סופית של טרמינלים (או סימני קלט), כאשר $V \cap \Sigma = \emptyset$.
$R$: קבוצה סופית של כללי ייצור (Production Rules), מהצורה $A \to \alpha$, כאשר $A \in V$ ו-$\alpha \in (V \cup \Sigma)^*$.
$S$: סימן ההתחלה, כאשר $S \in V$.

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

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

עץ גזירה (Parse Tree): ייצוג גרפי של גזירה, המראה את המבנה ההיררכי של המחרוזת. שורש העץ הוא סימן ההתחלה, העלים הם הטרמינלים המרכיבים את המחרוזת, וכל צומת פנימי הוא משתנה ש"נפתח" לפי כלל ייצור.

דקדוק דו-משמעי (Ambiguous Grammar): דקדוק שבו קיימת מחרוזת אחת לפחות בשפה שלה יש שני עצי גזירה שונים (או שתי גזירות שמאליות/ימניות שונות). דו-משמעות עלולה להוביל לפרשנויות שונות של אותה מחרוזת, ולכן יש להימנע ממנה בתכנון שפות תכנות.

אוטומטי מחסנית (PDA): מודל החישוב

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

אוטומט מחסנית (Pushdown Automaton - PDA): שישייה סדורה $M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$, כאשר:

$Q$: קבוצה סופית של מצבים.
$\Sigma$: אלפבית הקלט (קבוצת הטרמינלים).
$\Gamma$: אלפבית המחסנית (קבוצת הסימנים שניתן לדחוף למחסנית).
$\delta$: פונקציית המעברים, $Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma \to \mathcal{P}(Q \times \Gamma^*)$. פונקציה זו מקבלת מצב נוכחי, סימן קלט (או $\epsilon$), וסימן מראש המחסנית, ומחזירה קבוצה של זוגות (מצב חדש, מחרוזת לדחיפה למחסנית).
$q_0$: מצב ההתחלה, $q_0 \in Q$.
$Z_0$: סימן המחסנית ההתחלתי, $Z_0 \in \Gamma$.
$F$: קבוצה של מצבים מקבלים, $F \subseteq Q$.

ה-PDA פועל על ידי קריאת סימני קלט, שינוי מצב, וביצוע פעולות דחיפה (push) או שליפה (pop) מהמחסנית, בהתאם לסימן הקלט ולסימן שבראש המחסנית. ה-PDA הוא לא דטרמיניסטי באופן כללי.

קבלת מצב סופי (Acceptance by Final State)

ה-PDA מקבל מחרוזת קלט אם לאחר קריאת כל הקלט, הוא מגיע למצב מקבל (מצב ב-$F$). תוכן המחסנית אינו רלוונטי במקרה זה.

קבלת מחסנית ריקה (Acceptance by Empty Stack)

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

חשוב לדעת ששתי דרכי הקבלה הללו שקולות מבחינת כוח חישובי: לכל PDA המקבל בדרך אחת, קיים PDA אחר המקבל את אותה השפה בדרך השנייה.

הקשר בין CFG ל-PDA וצורת חומסקי

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

צורת חומסקי נורמלית (Chomsky Normal Form - CNF): צורה סטנדרטית לדקדוק חסר הקשר שבה כל כללי הייצור הם מהצורה $A \to BC$ או $A \to a$, כאשר $A, B, C$ הם משתנים ו-$a$ הוא טרמינל. כל דקדוק חסר הקשר שאינו מכיל את $\epsilon$ בשפה (או שמכיל $\epsilon$ וטופל באופן מיוחד) ניתן להמרה לצורת חומסקי נורמלית. צורה זו חשובה באלגוריתמים לניתוח תחבירי (parsing), כמו אלגוריתם CYK.

למה שאיבה לשפות חסרות הקשר: כלי להוכחה

למה השאיבה לשפות חסרות הקשר: זהו כלי קריטי במבחנים! למה השאיבה מאפשרת להוכיח ששפה אינה חסרת הקשר. הבנה מעמיקה של הלמה וכיצד ליישם אותה (בדרך כלל באמצעות הוכחה בדרך השלילה) היא חובה. זכרו את העיקרון: אם שפה $L$ היא חסרת הקשר, אז קיים מספר $p$ (אורך השאיבה) כך שלכל מחרוזת $s \in L$ שאורכה $|s| \ge p$, ניתן לפרק את $s$ לחמישה חלקים $s = uvwxy$ המקיימים את התנאים הבאים:

$|vwx| \le p$ (אורך החלק שניתן לשאיבה אינו עולה על $p$).
$|vx| \ge 1$ (לפחות אחד מהחלקים $v$ או $x$ אינו ריק).
לכל $i \ge 0$, המחרוזת $uv^iwx^iy$ נמצאת גם היא בשפה $L$.

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

שאלות לדיון

1. תנו דקדוק חסר הקשר לשפה $L = \{a^n b^m c^k \mid n=m \text{ או } m=k, n,m,k \ge 0\}$. האם הדקדוק שלכם דו-משמעי? נמקו.
2. בנו אוטומט מחסנית (PDA) עבור השפה $L = \{w c w^R \mid w \in \{a,b\}^*\}$, כאשר $w^R$ היא היפוך המחרוזת $w$. תארו את פעולתו של ה-PDA שבניתם.
3. הוכיחו באמצעות למה השאיבה ששפת כל המחרוזות מהצורה $a^n b^n c^n$ עבור $n \ge 0$ אינה שפה חסרת הקשר.
4. הסבירו את הקשר בין דקדוקים חסרי הקשר לאוטומטי מחסנית. מדוע שניהם נחשבים "חזקים יותר" מאשר אוטומטים סופיים?

נקודות לתשובת מודל

לשאלה 1: יש לבנות דקדוק המשלב שני מקרים (איחוד שפות) באמצעות כללי ייצור נפרדים עבור כל תנאי. לדוגמה, $S \to S_1 \mid S_2$, כאשר $S_1$ מייצר $a^n b^n c^k$ ו-$S_2$ מייצר $a^n b^m c^m$. יש לבדוק אם קיימת מחרוזת (למשל, $a^1 b^1 c^1$) שיכולה להיגזר בשתי דרכים שונות (דרך $S_1$ ודרך $S_2$) או בדרכים שונות בתוך אותו תת-דקדוק.
לשאלה 2: יש להגדיר את מרכיבי ה-PDA (מצבים, אלפבית קלט/מחסנית, פונקציית מעברים, מצב התחלה, סימן מחסנית התחלה, מצבים מקבלים). תיאור הפעולה צריך לכלול:
1. קריאת $w$ ודחיפת סימניו למחסנית.
2. קריאת הסימן $c$ (מעבר מצב ללא פעולת מחסנית, או פעולה סמלית).
3. קריאת $w^R$ והוצאת סימנים תואמים מהמחסנית.
4. קבלת המכונה כאשר המחסנית ריקה (או במצב מקבל) בסיום הקלט.
לשאלה 3: יש להניח בשלילה שהשפה $L = \{a^n b^n c^n \mid n \ge 0\}$ היא חסרת הקשר, ולכן קיימת $p$ כלשהי. יש לבחור מחרוזת $s = a^p b^p c^p$. כעת יש לנתח את כל המקרים האפשריים לפירוק $s = uvwxy$ המקיים את תנאי הלמה ($|vwx| \le p$, $|vx| \ge 1$). יש להראות שבכל מקרה, שאיבה (לרוב $i=0$ או $i=2$) תוביל למחרוזת שאינה בשפה (למשל, מספר ה-a-ים, b-ים או c-ים לא יהיה שווה).
לשאלה 4: יש להסביר את שקילות הכוח החישובי בין CFG ו-PDA: כל שפה שנוצרת על ידי CFG ניתנת לזיהוי על ידי PDA, ולהפך. ההסבר ל"חזקים יותר" צריך להתמקד ביכולת המחסנית של ה-PDA לזכור מידע "בלתי מוגבל" (בניגוד לאוטומט סופי שיש לו זיכרון סופי בלבד). יכולת זו מאפשרת לטפל בתלויות בנתונים קודמים (כמו התאמת סוגריים או $a^n b^n$), מה שאוטומטים סופיים אינם יכולים לעשות.

מצאתם טעות או שחסר משהו?