יחידה 3: תכונות של שפות רגולריות

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

שפות רגולריות: הגדרה וייצוגים

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

תכונות סגירות של שפות רגולריות

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

• איחוד (Union): אם L1 ו-L2 רגולריות, אז L1 ∪ L2 רגולרית.
• שרשור (Concatenation): אם L1 ו-L2 רגולריות, אז L1 · L2 רגולרית.
• כוכב קליני (Kleene Star): אם L רגולרית, אז L* רגולרית.
• משלים (Complement): אם L רגולרית, אז Lᶜ רגולרית.
• חיתוך (Intersection): אם L1 ו-L2 רגולריות, אז L1 ∩ L2 רגולרית. (ניתן להוכיח באמצעות דה-מורגן וסגירות לאיחוד ולמשלים, או בבניית אוטומט מכפלה).
• היפוך (Reversal): אם L רגולרית, אז Lᴿ רגולרית.

מגבלות של שפות רגולריות: למת הניפוח

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

שיטת הוכחה באמצעות למת הניפוח (בדרך השלילה):

1. הנחה בשלילה: נניח ש-L היא שפה רגולרית.
2. בחירת p: לפי למת הניפוח, קיים מספר p.
3. בחירת מילה s: נבחר מילה s ∈ L כך ש-|s| ≥ p, ובאופן שיקשה על הלמה להתקיים (לרוב, מילה "קשה" שחושפת את הצורך בזיכרון אינסופי).
4. פירוק s: לפי הלמה, s מתפרקת ל-xyz כאשר |y| > 0 ו-|xy| ≤ p.
5. ניפוח/כיווץ: נבחר i (לרוב i=0 או i=2) כך שהמילה xyⁱz אינה ב-L.
6. סתירה: הגענו לסתירה להנחה ש-L רגולרית. לכן, L אינה רגולרית.

דוגמה קלאסית: השפה L = {aⁿbⁿ | n ≥ 0} אינה רגולרית. נניח בשלילה ש-L רגולרית. קיים p. נבחר s = aᵖbᵖ. |s| = 2p ≥ p. לפי הלמה, s = xyz, כאשר |y| > 0 ו-|xy| ≤ p. מכיוון ש-|xy| ≤ p, החלק y חייב להיות מורכב כולו מ-'a'ים (או ריק, אבל |y|>0). כלומר, y = aᵏ עבור k > 0. ננפח את y פעם אחת (i=2): xy²z = x(aᵏ)aᵏz. המילה החדשה תהיה מהצורה aᵖ⁺ᵏbᵖ. מכיוון ש-k > 0, מספר ה-'a'ים אינו שווה למספר ה-'b'ים. לכן, xy²z ∉ L. זוהי סתירה! לכן, L אינה רגולרית.

שפות לא רגולריות נפוצות

הבנת דוגמאות לשפות לא רגולריות עוזרת להפנים את מגבלות האוטומטים הסופיים:

• {aⁿbⁿ | n ≥ 0}: דורשת ספירה והשוואה.
• {w | w מכילה מספר שווה של a's ו-b's}: דורשת ספירה מתמשכת.
• {ww | w ∈ {a,b}*}: דורשת "זכירת" מחצית המילה והשוואתה למחצית השנייה.
• {aⁿ | n הוא מספר ראשוני}: דורשת זיהוי תכונה מתמטית מורכבת.

שאלות לדיון

• הסבירו מדוע תכונות הסגירות חשובות בתכנון מנתחי לקסיקליים (Lexical Analyzers) בקומפיילרים.
• האם שפה סופית (שפה המכילה מספר סופי של מילים) יכולה להיות לא רגולרית? נמקו.
• הוכיחו באמצעות למת הניפוח שהשפה L = {aⁱbʲcᵏ | i=j או j=k} אינה רגולרית.
• תארו מצב מעשי בו ידע על מגבלות שפות רגולריות יכול למנוע טעות תכנונית.

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

• הוכחת אי-רגולריות באמצעות למת הניפוח:
  • הנחה בשלילה ש-L רגולרית.
  • קביעת p (מספר הניפוח).
  • בחירת מילה s מתאימה מ-L (אורך לפחות p) באופן אסטרטגי.
  • הסבר כיצד s מתפרקת ל-xyz לפי תנאי הלמה (|y|>0, |xy|≤p).
  • הצגת ניפוח/כיווץ (בחירת i) המוביל למילה שאינה ב-L.
  • הסקת סתירה והמסקנה ש-L אינה רגולרית.
• הבנת תכונות סגירות:
  • הגדרה ברורה של כל תכונה (איחוד, שרשור, כוכב קליני, משלים, חיתוך, היפוך).
  • הסבר קצר על משמעות הסגירות (התוצאה נשארת באותה מחלקת שפות).
• הבחנה בין שפות רגולריות ללא רגולריות:
  • שפות רגולריות: דפוסים פשוטים, ללא צורך ב"ספירה" או "השוואה" שרירותית.
  • שפות לא רגולריות: דורשות זיכרון אינסופי או יכולות ספירה/השוואה מורכבות.