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

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

שפות חסרות הקשר: רקע והגדרה

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

שפה חסרת הקשר (CFL): שפה שניתן לייצר באמצעות דקדוק חסר הקשר (CFG) או לזהות באמצעות אוטומט מחסנית (PDA). שפות אלו משמשות לתיאור התחביר של רוב שפות התכנות.

דקדוק חסר הקשר (CFG): רביעייה (V, Σ, R, S) כאשר V הוא קבוצת משתנים, Σ הוא האלפבית (טרמינלים), R הוא קבוצת כללי יצירה מהצורה A → β (כאשר A ∈ V ו-β ∈ (V ∪ Σ)*), ו-S ∈ V הוא סימן ההתחלה.

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

למת הניפוח לשפות חסרות הקשר

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

למת הניפוח (Pumping Lemma for CFLs): אם L היא שפה חסרת הקשר, אזי קיים מספר p (אורך הניפוח) כך שלכל מילה s ∈ L עם |s| ≥ p, ניתן לפרק את s לחמישה חלקים s = uvxyz כך שמתקיימים התנאים הבאים:

|vxy| ≤ p (החלק המנופח אינו ארוך מדי).
|vy| ≥ 1 (לפחות אחד מהחלקים v או y אינו ריק).
לכל i ≥ 0, המילה uvⁱxyⁱz ∈ L (החלקים v ו-y ניתנים לניפוח).

למת הניפוח - מוקד לבחינה: למת הניפוח היא אחד הכלים המרכזיים והנפוצים ביותר במבחנים להוכחה ששפה אינה שפה חסרת הקשר. חשוב מאוד להבין את ניסוחה הפורמלי ואת אופן השימוש בה. ההוכחה היא בדרך כלל הוכחה בשלילה: מניחים שהשפה היא CFL, מפעילים את הלמה, ומראים סתירה עבור בחירה חכמה של i. טעויות נפוצות כוללות בחירה לא נכונה של s, אי-התייחסות לכל המקרים האפשריים של v ו-y, או אי-הבנה של התנאים |vxy| ≤ p ו-|vy| ≥ 1.

תכונות סגור של שפות חסרות הקשר

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

איחוד (Union)

סגור: כן. אם L₁ ו-L₂ הן CFLs, אז L₁ ∪ L₂ היא גם CFL. ניתן לבנות CFG חדש המאחד את הדקדוקים הקיימים.

שרשור (Concatenation)

סגור: כן. אם L₁ ו-L₂ הן CFLs, אז L₁L₂ היא גם CFL. ניתן לבנות CFG חדש המשרשר את הדקדוקים הקיימים.

כוכב קלין (Kleene Star)

סגור: כן. אם L היא CFL, אז L* היא גם CFL. ניתן לבנות CFG חדש המאפשר חזרות על הדקדוק המקורי.

חיתוך עם שפה רגולרית

סגור: כן. אם L היא CFL ו-R היא שפה רגולרית, אז L ∩ R היא גם CFL. ניתן להשתמש באוטומט מחסנית ובאוטומט סופי במקביל.

חיתוך (Intersection)

אינו סגור: לא. קיימות שתי CFLs שחיתוכן אינו CFL. דוגמה קלאסית: L₁ = {aⁿbⁿc^m | n, m ≥ 0} ו-L₂ = {a^mbⁿcⁿ | n, m ≥ 0}. החיתוך הוא {aⁿbⁿcⁿ | n ≥ 0}, שאינה CFL.

משלים (Complement)

אינו סגור: לא. מכיוון שמחלקה זו אינה סגורה לחיתוך, ומתקיים L₁ ∩ L₂ = (L₁^c ∪ L₂^c)^c, אם היא הייתה סגורה למשלים, היא הייתה סגורה גם לחיתוך (בהינתן סגירות לאיחוד).

תכונות כריעות של שפות חסרות הקשר

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

בעיית הריקנות (Emptiness):

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

כריעה: כן. בהינתן שפה חסרת הקשר L ומילה w, ניתן לקבוע האם w ∈ L. ניתן לעשות זאת באמצעות אלגוריתם CYK, או על ידי סימולציה של PDA.
בעיית השקילות (Equivalence):

לא כריעה: לא. לא קיים אלגוריתם כללי הקובע האם שתי שפות חסרות הקשר L₁ ו-L₂ שקולות (כלומר, L₁ = L₂).
בעיית העמימות (Ambiguity):

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

שאלות לדיון

הוכח, באמצעות למת הניפוח, שהשפה L = {aⁿb^mcⁿ | n, m ≥ 0} אינה שפה חסרת הקשר.
האם מחלקת השפות חסרות הקשר סגורה תחת פעולת ההיפוך (Reverse)? נמק את תשובתך.
מדוע העובדה שבעיית השקילות עבור שפות חסרות הקשר אינה כריעה מהווה אתגר בתכנון מהדרים ובכלים לניתוח קוד?

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

למת הניפוח:
- הנח בשלילה ש-L היא CFL.
- בחר מילה s מתאימה מ-L שאורכה תלוי ב-p (לדוגמה, a^pb^pc^p או a^pb^pc^pd^p, בהתאם לשפה).
- פרט את כל המקרים האפשריים למיקום v ו-y בתוך s, תוך התחשבות בתנאי |vxy| ≤ p ו-|vy| ≥ 1.
- עבור כל מקרה, הראה כי ניפוח (i=0 או i=2) מוביל למילה שאינה ב-L, ובכך מגיע לסתירה.
תכונות סגור:
- להוכחת סגירות: הצג בנייה של דקדוק חסר הקשר (CFG) או אוטומט מחסנית (PDA) חדש המייצר/מזהה את השפה המתקבלת מהפעולה. לדוגמה, עבור איחוד, הוסף משתנה התחלה חדש S' → S₁ | S₂.
- להוכחת אי-סגירות: הצג דוגמה נגדית ספציפית של שפות מהמחלקה, שהפעלת הפעולה עליהן מניבה שפה שאינה במחלקה. לעיתים קרובות, ניתן להשתמש בלמת הניפוח כדי להוכיח שהשפה המתקבלת אינה CFL.
תכונות כריעות:
- להוכחת כריעות: תאר בקצרה אלגוריתם שפותר את הבעיה עבור כל קלט ומסיים תמיד.
- להוכחת אי-כריעות: בדרך כלל מתבצעת באמצעות רדוקציה מבעיה ידועה שאינה כריעה (לדוגמה, בעיית העצירה). בקורס זה, לרוב מספיק לציין שהבעיה אינה כריעה ולהבין את ההשלכות.

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