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

מה זאת "סגירות"?

אומרים שמשפחת שפות 𝒞 סגורה תחת פעולה ⊕ אם לכל L₁, L₂ ∈ 𝒞 גם L₁ ⊕ L₂ ∈ 𝒞. אם מצליחים להראות שניתן לבנות אוטומט (או ביטוי רגולרי) לתוצאה – זאת הוכחת סגירות.

הפעולות שתחתן השפות הרגולריות סגורות

1. איחוד L₁ ∪ L₂

נתונים שני NFAs N₁, N₂. בונים NFA חדש: מצב התחלתי q₀ חדש, ושני ε-מעברים – אחד למצב ההתחלתי של N₁ ואחד של N₂. כל אחד מהם מקבל בנפרד.

הוכחה אלגברית: אם r₁, r₂ ביטויים רגולריים, גם r₁ | r₂ הוא ביטוי רגולרי.

2. שרשור L₁ · L₂

בונים NFA: מצב התחלתי של N₁, ומכל מצב מקבל שלו ε-מעבר למצב ההתחלתי של N₂. מצבי הקבלה הסופיים הם של N₂ בלבד.

אלגברית: r₁ r₂ ביטוי רגולרי.

3. כוכבית קלייני L*

L* = ε ∪ L ∪ LL ∪ LLL ∪ … (חזרה 0 או יותר פעמים). בונים NFA חדש: מצב התחלתי חדש שגם מקבל (לטובת ε), עם ε-מעבר למצב ההתחלתי של N, ומכל מצב מקבל של N – ε-מעבר חזרה למצב ההתחלתי של N.

אלגברית: r* ביטוי רגולרי.

4. משלים L̄ = Σ* \ L

נתון DFA מלא (כל המעברים מוגדרים). פשוט מחליפים את F ל־Q \ F. מסלול אותו קלט מסתיים באותו מצב, אך עכשיו "מקבל" אם ורק אם המצב לא היה ב־F המקורית.

חשוב: חייב להתחיל מ־DFA (לא NFA), ושהמעברים יוגדרו על כל אות.

5. חיתוך L₁ ∩ L₂

בנייה של אוטומט־מכפלה. נתונים שני DFAs M₁ = (Q₁, Σ, δ₁, q₀¹, F₁) ו־M₂ = (Q₂, Σ, δ₂, q₀², F₂). מגדירים:

• Q = Q₁ × Q₂ (זוגות של מצבים)
• q₀ = (q₀¹, q₀²)
• δ((p, q), a) = (δ₁(p, a), δ₂(q, a))
• F = F₁ × F₂ – מקבל רק אם שניהם מקבלים

זה ה־DFA־מכפלה. עבור איחוד דרך אותה בנייה: F = (F₁ × Q₂) ∪ (Q₁ × F₂) – מקבל אם לפחות אחד מקבל. מציין שלא חייבים לעבור דרך NFA.

6. הפרש L₁ \ L₂

L₁ \ L₂ = L₁ ∩ L̄₂. שילוב של סגירות תחת חיתוך + משלים.

7. הפוך L^R

L^R = { wᴿ | w ∈ L } (כל מילה הפוכה). בונים NFA חדש: מהפכים את כיוון כל הקשתות, המצב ההתחלתי הופך להיות (יחיד) מקבל, ויוצרים מצב התחלתי חדש עם ε-מעברים אל מצבי הקבלה המקוריים.

8. הומומורפיזם וחזרה h(L), h^-1(L)

אם h: Σ → Δ* פונקציה ש"מחליפה כל אות במחרוזת", אז גם h(L) רגולרית. גם h^-1(L) רגולרית – ניתן להראות זאת באמצעות שינוי מסומן של δ.

טבלה מסכמת

איך משתמשים בזה בבגרות?

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

דוגמה: L = { w ∈ {a,b}* | w מתחילה ב־a וגם מסתיימת ב־b }. נסמן L₁ = "מתחילות ב־a" ו־L₂ = "מסתיימות ב־b". שתיהן רגולריות (קל לבנות לכל אחת DFA קטן). לכן L = L₁ ∩ L₂ רגולרית.

אזהרה: לא כל פעולה משמרת רגולריות

סגירות לא משחקת בכל המקרים. למשל אם L רגולרית, השפה { ww | w ∈ L } בדרך כלל אינה רגולרית. ל"הוכחת אי־סגירות" כזו ניעזר בלמת הניפוח – ראו הוכחת אי־רגולריות.