מודלים חישוביים
בנושא הזה כמעט לא כותבים קוד. מתארים "מכונות" פשוטות שקוראות מילה אות אחר אות ומחליטות אם לקבל אותה, ובודקים מה כל מכונה מסוגלת לעשות ומה לא.
במדויק: הנושא בנוי משלושה מודלים: אוטומט סופי (דטרמיניסטי, דטרמיניסטי לא מלא ולא דטרמיניסטי) ומשפחת השפות הרגולריות; אוטומט מחסנית דטרמיניסטי; ומכונת טיורינג, מודל לתכנית מחשב. בשאלון 899271 אלה שאלות 7-9 (בקיץ 2024: 9-11). שואלים בהן: אם מילה שייכת לשפה, אם שפה רגולרית ולמה, פעולות על שפות, בנייה או השלמה של אוטומט סופי ושל אוטומט מחסנית דטרמיניסטי, ומעקב אחר מכונת טיורינג או בנייה שלה.
אוטומט ומכונת טיורינג אפשר לתאר בציור או בטבלת מעברים. בסיכום הזה כל אוטומט מוצג כטבלת מעברים: שורה לכל מצב, עמודה לכל אות (או עמודה לכל רכיב של המעבר).
הכוח של כל מודל
כל מודל חזק מקודמו, כי יש לו יותר "זיכרון".
במדויק: לאוטומט סופי יש מספר סופי של מצבים, ולכן הוא זוכר רק מידע חסום: שארית, האות האחרונה, מונה עד קבוע. לאוטומט מחסנית יש גם מחסנית, ולכן הוא סופר בלי חסם: הוא מקבל למשל את aⁿbⁿ, שאינה רגולרית. מכונת טיורינג קוראת וכותבת בכל מקום בסרט, ולכן היא גם מחשבת פונקציות, למשל ההפרש בין שני מספרים.
1. תיאור מערכות ואוטומט סופי דטרמיניסטי
אוטומט סופי דטרמיניסטי
אוטומט הוא מכונה עם מספר סופי של מצבים. הוא קורא מילה אות אחר אות, ובכל אות עובר ממצב למצב. בסוף המילה הוא "עונה": אם הוא במצב מקבל, המילה מתקבלת; אחרת היא נדחית. כך מתארים מערכות (מנעול עם קוד, מכונת משקאות) ופותרים חידות.
במדויק: אוטומט סופי דטרמיניסטי מוגדר בחמישה רכיבים: א"ב Σ, קבוצה סופית של מצבים, מצב התחלתי אחד, קבוצת מצבים מקבלים, ופונקציית מעברים שנותנת לכל מצב ולכל אות מעבר אחד בדיוק. מסלול החישוב על מילה מתחיל במצב ההתחלתי ועובר לפי האותיות. אם הוא מסתיים במצב מקבל, זה מסלול חישוב מקבל והמילה מתקבלת. השפה של האוטומט היא כל המילים שהוא מקבל.
המושגים נולדים בתיאור מערכות: מצב, קלט, מעבר, מצב התחלתי, מצב מקבל ומצב מלכודת: מצב לא מקבל שכל המעברים ממנו חוזרים אליו. מילה שהגיעה אליו נדחית, מה שלא יבוא אחריה. בשיעור על מודלים נוספים תראו שאפשר לוותר עליו (אוטומט לא מלא).
טבלת מעברים
בטבלת מעברים יש שורה לכל מצב ועמודה לכל אות. בתא כותבים את המצב שעוברים אליו. מסמנים בחץ → את מצב ההתחלה, וליד כל מצב מקבל כותבים "(מקבל)". כדאי להוסיף עמודה של משמעות המצב.
דוגמה: המילים מעל {a, b} שיש בהן מספר זוגי של a.
| מצב | משמעות | a | b |
|---|---|---|---|
| → q0 (מקבל) | נקרא מספר זוגי של a | q1 | q0 |
| q1 | נקרא מספר אי-זוגי של a | q0 | q1 |
המילה abba: q0 –a→ q1 –b→ q1 –b→ q1 –a→ q0. המסלול מסתיים במצב המקבל q0, ולכן abba מתקבלת. ab מסתיימת ב-q1 ונדחית.
מה המצב זוכר: התבניות שחוזרות
| מה בודקים | מה המצב זוכר | כמה מצבים | בבגרות |
|---|---|---|---|
| זוגיות, או שארית בחלוקה ב-k | השארית עד עכשיו | k | זוגיות של מספר ה-a וה-c (2024); שארית של n + k בחלוקה ב-3 (2026) |
| רצף אסור או רצף מבוקש | האות האחרונה (או כמה אחרונות) | מספר האפשרויות | בלי ab ובלי bc (2024) |
| מבנה של בלוקים, כמו aⁿbᵐaᵏ | באיזה בלוק אנחנו | מספר הבלוקים | n, m, k > 0 (2025, 2026) |
| מונה חסום: "לפחות 3", "פחות מ-1000" | כמה נקראו, עד החסם | החסם ועוד אחד | מספר ה-a קטן מ-1000 (2026) |
| שני תנאים יחד | זוג: מה שזוכרים לכל תנאי | מכפלת המספרים | זוגיות × אות אחרונה = 6 מצבים (2024) |
בניית אוטומט: מה כל מצב זוכר
בודקים תמיד את המילה הריקה ε. בשפה של 2024 (בלי ab ובלי bc, ומספר ה-a וה-c יחד זוגי) ε שייכת: אין בה רצף אסור, ו-0 הוא מספר זוגי. לכן מצב ההתחלה q0 חייב להיות מקבל.
לפעמים מצב "ההתחלה" מתנהג בדיוק כמו מצב אחר, ואז הם מצב אחד. בשאלה של 2024 אין איסור אחרי c וגם לא בהתחלה, ולכן "התחלה" ו"זוגי, האות האחרונה c" הם אותו מצב q0, ומספיקים 6 מצבים.
דוגמה - אוטומט לשפה בלי הרצפים ab ו-bc
נתונה השפה L מעל הא"ב {a, b, c}:
L = {w | הרצפים ab, bc אינם מופיעים ב-w, ו-#a(w) + #c(w) הוא מספר זוגי}
#a(w) מציין את מספר המופעים של a במילה w, ו-#c(w) את מספר המופעים של c.
דוגמה למילה בשפה L היא cba: סכום המופעים של a (1) ושל c (1) הוא 2, מספר זוגי, והרצפים ab ו-bc אינם מופיעים בה.
(1) לפניכם חמש מילים: aaccc, aab, ε, baa, cbbba. בנוגע לכל אחת מהן ציינו אם היא שייכת לשפה L, ונמקו.
(2) בנו אוטומט סופי דטרמיניסטי שאינו מלא המקבל את השפה L.
| מילה | רצף ab או bc? | מספר ה-a וה-c | שייכת? |
|---|---|---|---|
| aaccc | לא | 2 + 3 = 5, אי-זוגי | לא |
| aab | כן, ab | 2 | לא |
| ε | לא | 0, זוגי | כן |
| baa | לא | 2, זוגי | כן |
| cbbba | לא | 1 + 1 = 2, זוגי | כן |
| מצב | משמעות | a | b | c |
|---|---|---|---|---|
| → q0 (מקבל) | זוגי; התחלה או האות האחרונה c | q3 | q4 | q1 |
| q1 | אי-זוגי; האות האחרונה c | q2 | q5 | q0 |
| q2 (מקבל) | זוגי; האות האחרונה a | q3 | – | q1 |
| q3 | אי-זוגי; האות האחרונה a | q2 | – | q0 |
| q4 (מקבל) | זוגי; האות האחרונה b | q3 | q4 | – |
| q5 | אי-זוגי; האות האחרונה b | q2 | q5 | – |
(1) שייכות: ε, baa, cbbba. לא שייכות: aab (מופיע ab), aaccc (5 מופעים של a ו-c, אי-זוגי).
(2) 6 מצבים (זוגיות × האות האחרונה), q0 התחלתי, מקבלים q0, q2, q4. מעברים: q0: a→q3, b→q4, c→q1; q1: a→q2, b→q5, c→q0; q2: a→q3, c→q1; q3: a→q2, c→q0; q4: a→q3, b→q4; q5: a→q2, b→q5. מעבר חסר = דחייה.
2. מילים ושפות פורמליות ופעולות על שפות
מילה ושפה
מילה היא רצף של אותיות, ושפה היא קבוצה של מילים. כל שאלה בנושא מתחילה בהגדרה של שפה, ולכן צריך לדעת לקרוא אותה ולבדוק אם מילה שייכת לה.
במדויק: א"ב Σ הוא קבוצה סופית של אותיות, למשל {a, b, c}. מילה היא רצף סופי של אותיות מהא"ב, ואורך המילה הוא מספר האותיות שבה. המילה הריקה ε היא המילה שאורכה 0. Σ* היא שפת כל המילים מעל Σ. שפה פורמלית היא קבוצה כלשהי של מילים מעל Σ, סופית או אינסופית. aⁿ פירושו n פעמים a ברצף: a³b² = aaabb.
שתי שפות קטנות שקל לבלבל ביניהן: ∅, השפה הריקה, שאין בה אף מילה; ו-{ε}, שפה עם מילה אחת, המילה הריקה. הסימון #a(w) פירושו מספר המופעים של a במילה w.
פעולות על שפות
בדוגמאות: A = {a, ab}, B = {b}, מעל הא"ב {a, b}.
| פעולה | סימון | המילים בשפה החדשה | דוגמה |
|---|---|---|---|
| איחוד | A ∪ B | מילה שב-A או ב-B | {a, ab, b} |
| חיתוך | A ∩ B | מילה שגם ב-A וגם ב-B | ∅ |
| משלים | L̅ | כל המילים ב-Σ* שאינן ב-L | המשלים של {ε}: כל המילים שאורכן 1 ומעלה |
| שרשור | A · B | xy, כש-x מ-A ו-y מ-B | {ab, abb} |
| חזקה | Lⁿ | שרשור של n מילים מ-L; L⁰ = {ε} | A² = {aa, aab, aba, abab} |
| היפוך | R(L) או Lᴿ | ההיפוך של כל מילה ב-L | R(A) = {a, ba} |
זהויות שכדאי לזכור
| זהות | נכונה תמיד? |
|---|---|
∅ · L = ∅ | כן: אין ב-∅ מילה לשרשר |
{ε} · L = L | כן: ε לא מוסיפה אותיות |
R(A · B) = R(B) · R(A) | כן: ההיפוך הופך גם את הסדר |
R(R(L)) = L | כן |
A · (B ∪ C) = (A · B) ∪ (A · C) | כן: שרשור מתפלג מעל איחוד |
A · B = B · A | לא: {a}·{b} = {ab}, אבל {b}·{a} = {ba} |
(A · B)ⁿ = Aⁿ · Bⁿ | לא: עם {a}, {b} ו-n = 2 יוצא {abab} מול {aabb} |
A ∩ (B · C) = (A ∩ B) · (A ∩ C) | לא: עם A = {ab}, B = {a}, C = {b} יוצא {ab} מול ∅ |
טענה על שפות: נכונה או לא נכונה
האם מילה שייכת לשפה
אל תבלבלו בין ∅ ל-{ε}. שרשור עם ∅ נותן ∅, ושרשור עם {ε} משאיר את השפה כמו שהיא. ב-2024: L₁ = ∅ ולכן L₁ · L₆ = ∅; L₃ = {ε} ולכן L₃ · L₄ = L₄.
קוראים כל תנאי בדיוק במקום שבו הוא כתוב. בשפה של 2026 התנאי n, m, k > 0 כתוב רק בשורה של n זוגי. לכן acccc (n = 1, m = 0, k = 4) שייכת: n אי-זוגי, ו-1 ≤ 0 + 4 − 2.
דוגמה א - חיתוך, היפוך ושרשור של שפות קטנות
לפניכם שש שפות מעל הא"ב {0, 1}. Σ* מציין את שפת כל המילים מעל הא"ב {0, 1}.
L₁ = ∅, L₂ = Σ*, L₃ = {ε}, L₄ = {0110}, L₅ = {ε, 110, 00, 001}, L₆ = {1, 0110, 110, 01}.
כתבו את השפה המתקבלת מכל אחת מהפעולות:
(1) L₅ ∩ L₆ (2) L₂ᴿ (3) L₁ · L₆ (4) L₃ · L₄ (5) L₄ · L₅
| מילה מ-L₅ | השרשור |
|---|---|
| ε | 0110 |
| 110 | 0110110 |
| 00 | 011000 |
| 001 | 0110001 |
(1) {110} (2) Σ* (כלומר L₂) (3) ∅ (4) {0110} (5) {0110, 0110110, 011000, 0110001}
דוגמה ב - טענות על היפוך, שרשור וחיתוך
נתונות שלוש שפות L₁, L₂, L₃ מעל הא"ב {a, b, c}. בנוגע לכל אחת מהטענות, קבעו אם היא נכונה או לא נכונה. אם היא נכונה, הסבירו מדוע; אם לא, הפריכו אותה בדוגמה נגדית: בחרו שפות ספציפיות והראו שעבורן הטענה לא מתקיימת.
(1) R(R(L₁) · R(L₂)) = L₁ · L₂
(2) L₁ · (L₂ ∪ L₃) = (L₁ · L₂) ∪ (L₁ · L₃)
(3) L₁ ∩ (L₂ · L₃) = (L₁ ∩ L₂) · (L₁ ∩ L₃)
R(R(L₁) · R(L₂)) = L₂ · L₁. דוגמה נגדית: L₁ = {a}, L₂ = {b}. באגף שמאל R({a}·{b}) = R({ab}) = {ba}; באגף ימין {ab}. השפות שונות.(1) לא נכונה: אגף שמאל שווה ל-L₂ · L₁. עם L₁ = {a}, L₂ = {b}: אגף שמאל {ba}, אגף ימין {ab}.
(2) נכונה: שרשור מתפלג מעל איחוד (הכלה בשני הכיוונים).
(3) לא נכונה: עם L₁ = {ab}, L₂ = {a}, L₃ = {b}: אגף שמאל {ab}, אגף ימין ∅.
3. שפות רגולריות ולא רגולריות
שפה רגולרית
יש שפות שאוטומט סופי יכול לזהות, ויש כאלה שלא, כי הזיכרון שלו, המצבים, סופי. בבגרות שואלים על שפה נתונה: האם היא רגולרית, ולמה.
במדויק: שפה רגולרית אם יש אוטומט סופי דטרמיניסטי שמקבל אותה, ולא רגולרית אם אין אוטומט כזה. הסימן המובהק לשפה לא רגולרית: כדי להחליט צריך לזכור מספר לא חסום ולהשוות אותו למספר אחר, כמו בשפה {aⁿbⁿ | n ≥ 0}. כל שפה סופית היא רגולרית: אפשר לבנות אוטומט עם מסלול לכל מילה.
הנימוק שמאחורי "האוטומט צריך לזכור את n": נניח שיש אוטומט עם p מצבים לשפה {aⁿbᵐaᵏ | n, m, k > 0, n = k}. בין המילים a¹b, a²b, ..., aᵖ⁺¹b יש שתיים, aⁱb ו-aʲb עם i ≠ j, שמסתיימות באותו מצב. מאותו מצב ההמשך זהה, ולכן האוטומט מקבל או דוחה יחד את aⁱbaⁱ ואת aʲbaⁱ. אבל הראשונה בשפה והשנייה לא. בשאלות כתוב בדרך כלל "די בהסבר מילולי".
רגולרית או לא: איך מזהים
| מה השפה דורשת | רגולרית? | בבגרות |
|---|---|---|
| מספר סופי של מילים (כל הכמויות חסומות) | כן: כל שפה סופית רגולרית | n + m + k < 100 (2025); k < 1000 < n < 2000 (2026) |
| זוגיות או שארית של כמות | כן | n % 2 = k % 2 (2025) |
| השוואה בין כמות חסומה לכמות אחרת | כן: סופרים במצבים עד החסם | aⁿbᵏcⁿ עם n < 1000 < k (2026) |
| כמות לא חסומה שרק צריכה להיות גדולה מקבוע | כן | k > 1000 (2026) |
| השוואה בין שתי כמויות לא חסומות | לא | n = k (2025); aⁿbᵏcⁿ עם k < 1000 < n (2026) |
תכונות הסגירות של השפות הרגולריות
אם L₁ ו-L₂ רגולריות, גם השפות האלה רגולריות:
| פעולה | למה |
|---|---|
| משלים L̅₁ | באוטומט מלא ל-L₁ מחליפים בין מצבים מקבלים ללא מקבלים |
| חיתוך L₁ ∩ L₂ | אוטומט מכפלה: מצב = זוג (מצב של האוטומט של L₁, מצב של האוטומט של L₂), מקבל כששניהם מקבלים |
| איחוד L₁ ∪ L₂ | אותו אוטומט מכפלה, מקבל כשלפחות אחד מהם מקבל |
| הפרש L₁ − L₂ | זה חיתוך עם המשלים: L₁ ∩ L̅₂ |
| שרשור L₁ · L₂, היפוך R(L₁) | בעזרת אוטומט לא דטרמיניסטי |
הסגירות אומרת מה קורה כשמתחילים מרגולריות. על שפות לא רגולריות היא לא אומרת כלום.
מה לא נובע מהסגירות
| טענה | נכונה? | דוגמה נגדית מהבגרות |
|---|---|---|
| חיתוך של שתי שפות לא רגולריות לא רגולרי | לא | {aⁿbⁿ} ∩ {bⁿaⁿ} = {ε} (2024) |
| חיתוך של שפה לא רגולרית עם שפה סופית לא רגולרי | לא: התוצאה סופית | L₁ ∩ L₃ (2025) |
| תת-שפה של שפה לא רגולרית לא רגולרית | לא | L₃ חלק מ-L₂, ו-L₃ סופית (2026) |
| איחוד של רגולרית ולא רגולרית רגולרי | לא בהכרח | L₁ ∪ L₂ לא רגולרית (2026) |
נימוק: רגולרית או לא
מה שקובע הוא אם הכמות חסומה, לא אם מופיע aⁿ...cⁿ. ב-2026 aⁿbᵏcⁿ עם n < 1000 רגולרית: האוטומט סופר עד 999 a במצבים. אותה צורה עם n > 1000 לא רגולרית.
את המשלים לוקחים ביחס ל-Σ*, כל המילים מעל הא"ב, ולא רק ביחס למילים "בצורה הנכונה". ב-2025 המשלים של L₃ (המילים aⁿbᵐaᵏ עם n + m + k < 100) כולל גם את ba ואת bbb.
דוגמה א - רגולריות של שלוש שפות עם חסמים
לפניכם שלוש שפות L₁ – L₃ מעל הא"ב {a, b, c}:
L₁ = {aⁿbᵏcⁿ | 0 < n < 1000 < k}
L₂ = {aⁿbᵏcⁿ | 0 < k < 1000 < n}
L₃ = {aⁿbᵏcⁿ | 0 < k < 1000 < n < 2000}
בנוגע לכל אחת מהשפות, כתבו אם היא רגולרית או לא. נמקו את תשובתכם (די בהסבר מילולי; אין צורך באוטומט).
| שפה | n | k | צריך להשוות |
|---|---|---|---|
| L₁ | חסום (קטן מ-1000) | לא חסום | את מספר ה-c ל-n החסום |
| L₂ | לא חסום (גדול מ-1000) | חסום | את מספר ה-c ל-n הלא חסום |
| L₃ | חסום (קטן מ-2000) | חסום | הכול חסום |
L₁ רגולרית (n חסום); L₂ לא רגולרית (צריך להשוות את מספר ה-c ל-n לא חסום); L₃ רגולרית (סופית).
דוגמה ב - רגולריות של חיתוך, איחוד ומשלימים
נתונות השפות מעל הא"ב {a, b, c}:
L₁ = {aⁿbᵏcⁿ | 0 < n < 1000 < k} (רגולרית)
L₂ = {aⁿbᵏcⁿ | 0 < k < 1000 < n} (לא רגולרית)
L₃ = {aⁿbᵏcⁿ | 0 < k < 1000 < n < 2000} (סופית)
R(L) היא השפה ההפוכה, ו-L̅ היא המשלים.
L₄ = L₂ ∩ R(L₂)
L₅ = L₁ ∪ L₂
L₆ = L̅₁ ∪ L̅₃
בנוגע לכל אחת מהשפות L₄ – L₆, כתבו אם היא רגולרית או לא, ונמקו (די בהסבר מילולי).
L₄ = ∅, רגולרית; L₅ לא רגולרית; L₆ = Σ* (כל המילים), רגולרית.
4. מודלים נוספים: אוטומט לא מלא ואוטומט לא דטרמיניסטי
אוטומט לא מלא ואוטומט לא דטרמיניסטי
משנים קצת את ההגדרה של האוטומט ומקבלים מודל חדש. בתכנית שני שינויים: לוותר על מעברים (אוטומט לא מלא), ולאפשר כמה מעברים באותה אות (אוטומט לא דטרמיניסטי). קל יותר לבנות אותם, והם מקבלים בדיוק את אותן שפות.
במדויק: באוטומט סופי דטרמיניסטי לא מלא יש לכל מצב ולכל אות לכל היותר מעבר אחד. אם אין מעבר לאות שנקראה, האוטומט נתקע והמילה נדחית. באוטומט סופי לא דטרמיניסטי יכולים לצאת ממצב אחד כמה מעברים באותה אות, והמילה מתקבלת אם יש לפחות מסלול חישוב אחד שקורא את כל המילה ומסתיים במצב מקבל. המודלים שקולים: לכל אוטומט סופי לא דטרמיניסטי יש אוטומט סופי דטרמיניסטי שמקבל את אותה שפה.
מאוטומט לא מלא עוברים למלא בקלות: מוסיפים מצב מלכודת אחד, ושולחים אליו כל מעבר חסר (וגם את כל המעברים של המלכודת עצמה). בגלל השקילות, אוטומט לא דטרמיניסטי עוזר להראות שהשפות הרגולריות סגורות לשרשור, להיפוך ולאיחוד: הוא יכול "לנחש", למשל, איפה נגמר החלק הראשון של המילה. בשאלות הבגרות של 2024-2026 ביקשו לבנות או להשלים אוטומט סופי דטרמיניסטי שאינו מלא.
מלא, לא מלא, לא דטרמיניסטי
| מודל | מעברים לכל מצב ואות | המילה נדחית כש... |
|---|---|---|
| דטרמיניסטי מלא | בדיוק אחד | המסלול מסתיים במצב לא מקבל (למשל במלכודת) |
| דטרמיניסטי לא מלא | אפס או אחד | חסר מעבר, או שהמסלול מסתיים במצב לא מקבל |
| לא דטרמיניסטי | כל מספר | אף מסלול לא קורא את כל המילה ומסתיים במצב מקבל |
השלמת אוטומט נתון
בשאלת השלמה כתוב: "אין להוסיף בו מצבים או מעברים, ואין לשנות את סימני הקלט המופיעים בו. תשובה שיהיה בה שינוי באוטומט הנתון לא תזכה בנקודות." משלימים רק את מה שחסר.
כשמבקשים אוטומט שאינו מלא, לא צריך מצב מלכודת: מעבר שאחריו המילה בוודאות לא בשפה פשוט לא כותבים. ב-2024 אין מ-q2 (האות האחרונה a) מעבר ב-b, כי ab אסור.
דוגמה - השלמת תוויות ומצבים מקבלים באוטומט לא מלא
נתונה השפה L מעל הא"ב {a, b, c}:
L = {aᵐbᵏcˣ | m, k, x > 0 וגם (m%2 = k%2 או m%2 = x%2)}
כל אחת מהאותיות a, b, c מופיעה פעם אחת לפחות, לפי הסדר. אם מספר ה-a זוגי (אי-זוגי), גם מספר ה-b או מספר ה-c זוגי (אי-זוגי). דוגמאות למילים בשפה: abbbbccc, aaaabbc. דוגמה למילה שאינה בשפה: aabc.
נתון אוטומט סופי דטרמיניסטי שאינו מלא המקבל את L. מצב ההתחלה q0.
הוסיפו את סימני הקלט החסרים וסמנו את המצבים המקבלים. אין להוסיף מצבים או מעברים, ואין לשנות את סימני הקלט המופיעים.
| מצב | a | b | c | מקבל? |
|---|---|---|---|---|
| → q0 | q1 | – | – | לא |
| q1 | q2 | q3 | – | לא |
| q2 | q1 | q5 | – | לא |
| q3 | – | q4 | q10 | לא |
| q4 | – | q3 | q8 | לא |
| q5 | – | q6 | q7 | לא |
| q6 | – | q5 | q10 | לא |
| q7 | – | – | q8 | לא |
| q8 | – | – | q9 | כן |
| q9 | – | – | q8 | לא |
| q10 | – | – | q10 | כן |
q2→q1: a; q3→q4: b; q4→q3: b; q5→q6: b; q6→q5: b; q3→q10: c; q6→q10: c; q4→q8: c; q7→q8: c; q8→q9: c; q9→q8: c; q10→q10: c. מצבים מקבלים: q8, q10.
5. אוטומט מחסנית דטרמיניסטי
אוטומט מחסנית דטרמיניסטי
אוטומט סופי לא יכול לספור בלי חסם. אם מוסיפים לו מחסנית, מבנה שבו מכניסים ומוציאים רק מלמעלה, הוא יכול: דוחפים סימן על כל a, ושולפים סימן על כל b.
במדויק: באוטומט מחסנית כל מעבר תלוי במצב, באות שנקראת ובסימן שבראש המחסנית (או בכך שהמחסנית ריקה). המעבר קובע מצב חדש ופעולה על המחסנית: דחוף סימן, שלוף את הסימן שבראש, או ללא שינוי. האוטומט דטרמיניסטי: בכל רגע ברור איזה מעבר לבצע, כלומר לכל מצב, אות וראש מחסנית יש לכל היותר מעבר אחד. באוטומט שבשאלון 2026 כל מעבר קורא אות, וכך בונים גם בסיכום הזה. צירוף שאין לו מעבר: האוטומט נתקע והמילה נדחית. המילה מתקבלת אם בסוף הקלט האוטומט במצב מקבל.
אוטומט מחסנית דטרמיניסטי חזק מאוטומט סופי: הוא מקבל שפות לא רגולריות, כמו aⁱbʲcⁱ⁻ʲ (2025) ו-(ab)ᵏcᵐbᵐ⁺³ᵏ (2024). במיקוד תשפ"ז נכלל רק אוטומט המחסנית הדטרמיניסטי: בונים אוטומט שבו בכל רגע ברור איזה מעבר לבצע, בלי ניחושים.
סימון המעברים
על חץ כותבים אות, ראש המחסנית / פעולה:
| מעבר | המשמעות |
|---|---|
| a, מחסנית ריקה / דחוף S | קוראים a כשהמחסנית ריקה, ודוחפים S |
| a, A / דחוף A | קוראים a כש-A בראש, ודוחפים עוד A |
| b, A / שלוף | קוראים b כש-A בראש, ושולפים אותו |
| c, S / ללא שינוי | קוראים c כש-S בראש, והמחסנית לא משתנה |
בטבלת מעברים כותבים עמודה לכל רכיב: מצב, אות, ראש המחסנית, פעולה, מצב חדש. בחלק מהפתרונות מסמנים את תחתית המחסנית בסימן מיוחד ⊥, וראש מחסנית ⊥ פירושו מחסנית ריקה. זה אותו דבר.
תבניות של מחסנית
| מה השפה דורשת | מה עושים במחסנית | בבגרות |
|---|---|---|
| שוויון: מספר ה-b שווה למספר ה-a | דוחפים על כל a, שולפים על כל b | aⁿbⁿ |
| סכום: מספר ה-b ועוד מספר ה-c שווה למספר ה-a | דוחפים על כל a, שולפים על כל b ועל כל c | aⁱbʲcⁱ⁻ʲ (2025) |
| משקל: 3 לכל ab ו-1 לכל c | דוחפים 3 סימנים על כל ab ואחד על כל c, שולפים על כל b | (ab)ᵏcᵐbᵐ⁺³ᵏ (2024) |
| חצי: n = m/2 + k | b ראשון בכל זוג ללא שינוי, b שני שולף; כל c שולף | 2026 |
| מונה חסום ("לפחות 3 c") או זוגיות | סופרים במצבים, לא במחסנית | 2025, 2026 |
| לדעת מתי המחסנית מתרוקנת | הסימן הראשון שנדחף מיוחד (X, Y או S). המעבר ששולף אותו עובר למצב המקבל | 2024, 2025, 2026 |
בניית אוטומט מחסנית דטרמיניסטי
בשפה של 2024, (ab)ᵏcᵐbᵐ⁺³ᵏ עם k, m ≥ 0, המילה הריקה ε שייכת (k = m = 0). לכן מצב ההתחלה q0 הוא גם מצב מקבל.
מעבר צריך לפעול עם כל סימן שיכול להיות בראש המחסנית באותו רגע. ב-2026, אחרי a אחד יש במחסנית רק S, ואחרי 3 a הראש הוא A. לכן על המעברים שאחרי q1 כותבים שתי תוויות, למשל "b, A / ללא שינוי" וגם "b, S / ללא שינוי". מי שכותב רק A דוחה את abbc, שבשפה.
אחרי שהסימן המיוחד נשלף, אסור שתבוא אות נוספת, ולכן אין מעברים יוצאים מהמצב המקבל. ב-2025 aaaacccccc נדחית: אחרי ש-f מתקבל, מגיע עוד c ואין לו מעבר.
דוגמה א - בניית אוטומט מחסנית לשפה aⁱbʲcⁱ⁻ʲ
נתונה השפה L מעל הא"ב {a, b, c}:
L = {aⁱbʲcⁱ⁻ʲ | i ≥ 4, (i − j) ≥ 3}
בנו אוטומט מחסנית דטרמיניסטי המקבל את השפה L.
| מצב | אות | ראש המחסנית | פעולה | מצב חדש | הסבר |
|---|---|---|---|---|---|
| q0 | a | ריקה | דחוף X | qa | ה-a הראשון |
| qa | a | X | דחוף A | qa | עוד a |
| qa | a | A | דחוף A | qa | עוד a |
| qa | b | A | שלוף | qb | b ראשון |
| qb | b | A | שלוף | qb | עוד b |
| qa | c | A | שלוף | p1 | c ראשון, אין b |
| p1 | c | A | שלוף | p2 | c שני |
| p2 | c | A | שלוף | p3 | c שלישי |
| p3 | c | A | שלוף | p4 | c רביעי ומעלה |
| p4 | c | A | שלוף | p4 | |
| p3 | c | X | שלוף | f | c רביעי והאחרון |
| p4 | c | X | שלוף | f | c אחרון (חמישי ומעלה) |
| qb | c | A | שלוף | r1 | c ראשון אחרי b |
| r1 | c | A | שלוף | r2 | c שני |
| r2 | c | A | שלוף | r3 | c שלישי ומעלה |
| r3 | c | A | שלוף | r3 | |
| r2 | c | X | שלוף | f | c שלישי והאחרון |
| r3 | c | X | שלוף | f | c אחרון (רביעי ומעלה) |
| נקרא | מצב | מחסנית (הראש מימין) |
|---|---|---|
| התחלה | q0 | ריקה |
| a | qa | X |
| a | qa | XA |
| a | qa | XAA |
| a | qa | XAAA |
| b | qb | XAA |
| c | r1 | XA |
| c | r2 | X |
| c | f | ריקה |
סוף הקלט במצב f, המילה מתקבלת. דחיות: aaaaccc (בלי b ורק 3 c: הקלט נגמר ב-p3 עם X במחסנית, ו-p3 לא מקבל); aaaabbcc (i − j = 2: ב-r1 נקרא c כש-X בראש, אין מעבר).
דוחפים X עבור ה-a הראשון ו-A עבור כל a נוסף; כל b שולף A; כל c שולף; ה-c ששולף את X עובר למצב המקבל f, בתנאי שנקראו לפחות 3 c (אם היו b) או לפחות 4 c (אם לא היו b). טבלת המעברים בפתרון.
דוגמה ב - השלמת ראש המחסנית והפעולה במעברים
נתונה השפה L מעל הא"ב {a, b, c}:
L = {aⁿbᵐcᵏ}, כאשר:
לפניכם אוטומט מחסנית דטרמיניסטי המקבל את L. מצב ההתחלה q0. המעברים בין q0 ל-q1 נתונים במלואם:
בשאר המעברים מופיעה רק האות:
| מעבר | מ- → אל | אות |
|---|---|---|
| 1-3 | q0 → q2, q2 → q3, q3 → q2 | b |
| 4-7 | q3 → q6, לולאה ב-q6, q3 → q9, q6 → q9 | c |
| 8-12 | q1 → q4 (b), q1 → q5 (c), q4 → q7 (b), q4 → q8 (c), q5 → q8 (c) | b או c |
| 13-15 | לולאה ב-q7 (b), q7 → q8 (c), לולאה ב-q8 (c) | b או c |
| 16-21 | q7 → q10 (b), q7 → q11 (c), q8 → q11 (c), לולאה ב-q10 (b), q10 → q11 (c), לולאה ב-q11 (c) | b או c |
השלימו לכל מעבר ממוספר את האות שבראש המחסנית ואת הפעולה (דחוף, שלוף או ללא שינוי), וכתבו מה הם המצבים המקבלים.
| מעבר | אות | ראש המחסנית / פעולה |
|---|---|---|
| 1 (q0 → q2) | b | A / ללא שינוי |
| 2 (q2 → q3) | b | A / שלוף |
| 3 (q3 → q2) | b | A / ללא שינוי |
| 4 (q3 → q6) | c | A / שלוף |
| 5 (לולאה ב-q6) | c | A / שלוף |
| 6 (q3 → q9) | c | S / שלוף |
| 7 (q6 → q9) | c | S / שלוף |
| 8-12 | b או c | A / ללא שינוי, וגם S / ללא שינוי |
| 13 (לולאה ב-q7) | b | A / שלוף |
| 14 (q7 → q8) | c | A / שלוף |
| 15 (לולאה ב-q8) | c | A / שלוף |
| 16-21 | b או c | S / ללא שינוי |
| מילה | המסלול (המחסנית, הראש מימין) | תוצאה |
|---|---|---|
| aabbc | q1 [S], q0 [SA], q2 [SA], q3 [S], q9 [ריקה] | מתקבלת |
| abbc | q1 [S], q4 [S], q7 [S], q11 [S] | מתקבלת |
| aaabbc | q1 [S], q0 [SA], q1 [SAA], q4, q7 [SAA], q8 [SA] | נדחית: q8 לא מקבל |
(1) b, A/ללא שינוי (2) b, A/שלוף (3) b, A/ללא שינוי (4) c, A/שלוף (5) c, A/שלוף (6) c, S/שלוף (7) c, S/שלוף (8)-(12) ללא שינוי, גם כש-A בראש וגם כש-S בראש (13) b, A/שלוף (14) c, A/שלוף (15) c, A/שלוף (16)-(21) ראש S/ללא שינוי. מצבים מקבלים: q9, q10, q11.
6. מכונת טיורינג
מכונת טיורינג
מכונת טיורינג היא מודל לתכנית מחשב. בניגוד לאוטומט, היא כותבת על הסרט, זזה ימינה ושמאלה וחוזרת לקרוא שוב. לכן היא לא רק מקבלת מילים: היא גם מחשבת, כלומר מקבלת מספר או מילה על הסרט ומשאירה עליו תוצאה.
במדויק: יש סרט של תאים שמתחיל בסימן תחילת הסרט (⊣ או ⊢), אחריו הקלט ואחריו תאים ריקים Δ. הראש נמצא מעל תא אחד. מעבר נכתב x / y, R: אם במצב הנוכחי הראש קורא x, כותבים y במקומו, זזים תא ימינה (R) או שמאלה (L), ועוברים למצב חדש. המכונה עוצרת כשאין מעבר מתאים. אם עצרה במצב מקבל, המילה מתקבלת. מספר בייצוג אונרי הוא רצף של אחדות: 4 = 1111.
מכונה יכולה גם לא לעצור לעולם, ואז היא לא מקבלת את המילה. לפי התיזה של צ'רץ' וטיורינג, כל מה שאפשר לחשב בתכנית מחשב אפשר לחשב במכונת טיורינג.
טבלת מעברים וטבלת מעקב
טבלת מעברים: שורה לכל חץ. למשל שלושת המעברים שיוצאים מ-q0 במכונה של 2026:
| מצב | קורא | כותב | תזוזה | מצב חדש |
|---|---|---|---|---|
| q0 | b | b | R | q0 |
| q0 | a | Δ | R | q1 |
| q0 | Δ | Δ | L | q5 |
טבלת מעקב: שורה לכל שלב, עם המצב ותוכן הסרט; התא שמתחת לראש מסומן בסוגריים מרובעים. המעקב של אותה מכונה על המילה bb:
| שלב | מצב | תא 0 | תא 1 | תא 2 | תא 3 |
|---|---|---|---|---|---|
| 0 | q0 | ⊣ | [b] | b | Δ |
| 1 | q0 | ⊣ | b | [b] | Δ |
| 2 | q0 | ⊣ | b | b | [Δ] |
| 3 | q5 | ⊣ | b | [b] | Δ |
טכניקות שחוזרות
| טכניקה | איך | בבגרות |
|---|---|---|
| דילוג | לולאה x / x, R עד שמגיעים לסימן אחר | q0 מדלג על b (2026) |
| חזרה לתחילת הסרט | זזים שמאלה עד סימן תחילת הסרט, ואז צעד ימינה | 2025 |
| בדיקת זוגיות | שני מצבים שמתחלפים בכל 1 | 2025 |
| סימון | מחליפים 1 בסימן אחר (x, Y) כדי לזכור שהוא טופל | 2025 |
| סבבים בזוגות | בכל סבב מוחקים או מסמנים 1 משני הצדדים, עד שצד אחד נגמר | הפרש (2024), חצי (2025) |
| הזזה שמאלה | מוחקים אות, חוזרים תא אחד וכותבים אותה שם; מצב נפרד לכל אות שנזכרת | 2026 |
מעקב אחר מכונת טיורינג
בניית מכונת טיורינג
שאלה על "האם המכונה פועלת נכון" בודקת מקרי קצה. במכונת ההפרש של 2024, כשהמספר השני 0 (הסרט 11#), המצב q6 מגיע לתא של סימן תחילת הסרט ואין לו עליו מעבר. המכונה נתקעת ב-q6, שאינו מצב העצירה q7, ולכן היא לא פועלת נכון.
הראש מתחיל במקום שהשאלה מראה. ב-2026 הוא מתחיל על האות הראשונה (תא 1), מימין לסימן תחילת הסרט. כשהשאלה לא מראה, בודקים במכונה: ב-2024 אין ל-q0 מעבר על ⊢, ולכן גם שם הראש מתחיל בתא 1.
"כתבו מה המכונה עושה" היא שאלה על כל קלט, לא על הדוגמה. ב-2026 התשובה: המכונה מוחקת את ה-a הראשון ומזיזה את כל מה שאחריו תא שמאלה; מילה בלי a לא משתנה; והמכונה מקבלת כל מילה.
דוגמה א - מעקב אחר מכונה שמוחקת את ה-a הראשון
נתונה מכונת טיורינג המקבלת מילים מעל הא"ב {a, b} (R = ימין, L = שמאל). מצב ההתחלה q0, והמצב המקבל q5. בתחילה הראש על התא שמימין לסימן ⊣ (תא 1).
| מצב | קורא | כותב | תזוזה | מצב חדש |
|---|---|---|---|---|
| q0 | b | b | R | q0 |
| q0 | a | Δ | R | q1 |
| q0 | Δ | Δ | L | q5 |
| q1 | Δ | Δ | R | q5 |
| q1 | b | Δ | L | q3 |
| q1 | a | Δ | L | q2 |
| q2 | Δ | a | R | q4 |
| q3 | Δ | b | R | q4 |
| q4 | Δ | Δ | R | q1 |
(1) עקבו אחרי פעולת המכונה בעבור המילה aba. במעקב יש להראות בכל שלב את הסרט, מעל איזה תא נמצא הראש, ובאיזה מצב המכונה.
(2) כתבו בקצרה מה המכונה עושה.
| שלב | מצב | תא 0 | תא 1 | תא 2 | תא 3 | תא 4 | תא 5 |
|---|---|---|---|---|---|---|---|
| 0 | q0 | ⊣ | [a] | b | a | Δ | Δ |
| 1 | q1 | ⊣ | Δ | [b] | a | Δ | Δ |
| 2 | q3 | ⊣ | [Δ] | Δ | a | Δ | Δ |
| 3 | q4 | ⊣ | b | [Δ] | a | Δ | Δ |
| 4 | q1 | ⊣ | b | Δ | [a] | Δ | Δ |
| 5 | q2 | ⊣ | b | [Δ] | Δ | Δ | Δ |
| 6 | q4 | ⊣ | b | a | [Δ] | Δ | Δ |
| 7 | q1 | ⊣ | b | a | Δ | [Δ] | Δ |
| 8 | q5 | ⊣ | b | a | Δ | Δ | [Δ] |
(1) 9 שלבים (0-8); המכונה עוצרת ב-q5, המילה מתקבלת, ועל הסרט נשאר ba.
(2) המכונה מוחקת מהמילה את המופע הראשון של a ומזיזה את האותיות שאחריו תא שמאלה; אם אין a, המילה לא משתנה. המכונה מקבלת כל מילה.
דוגמה ב - בניית מכונה: חצי המספר או המספר פחות 1
כתבו מכונת טיורינג המקבלת בתחילת הסרט מספר אונרי הגדול מאחד, ומחזירה מספר חדש:
הנחיות: אין צורך לשמור על הקלט (אפשר לשנות את הקלט לסימנים שונים). המספר המוחזר יופיע במקום כלשהו בסרט בין שני סימני דולר. אין צורך לבדוק את תקינות הקלט.
הסרטים בדוגמאות שבשאלה, לפני ההרצה ואחריה:
6: ⊢ 1 1 1 1 1 1 Δ Δ ... -> ... $ 1 1 1 $
5: ⊢ 1 1 1 1 1 Δ Δ ... -> ... $ 1 1 1 1 $q0: ⊢ / ⊢, R -> qE
qE: 1 / 1, R -> qO qE: Δ / Δ, L -> e0
qO: 1 / 1, R -> qE qO: Δ / Δ, L -> o0
o0: 1 / 1, L -> o0 o0: ⊢ / ⊢, R -> o1
o1: 1 / $, R -> o2
o2: 1 / 1, R -> o2 o2: Δ / $, R -> h
e0: 1 / 1, L -> e0 e0: ⊢ / ⊢, R -> e1
e1: x / x, R -> e1 e1: 1 / x, R -> e2 e1: Y / Y, L -> f1
e2: 1 / 1, R -> e2 e2: Y / Y, L -> e3 e2: Δ / Δ, L -> e3
e3: 1 / Y, L -> e4
e4: 1 / 1, L -> e4 e4: x / x, R -> e1
f1: x / $, R -> f2
f2: Y / 1, R -> f2 f2: Δ / $, R -> hn = 6:
⊢111111 (qE -> e0)
⊢x1111Y
⊢xx11YY
⊢xxxYYY (e1 -> f1)
⊢xx$YYY
⊢xx$111$ (h)
n = 5:
⊢11111 (qO -> o0)
⊢$1111
⊢$1111$ (h)בין שני סימני הדולר: 3 = 6/2 ו-4 = 5 − 1, כמו בדוגמאות.
בודקים זוגיות במעבר אחד ימינה. אי-זוגי: ה-1 הראשון הופך לסימן דולר, וכותבים סימן דולר בתא הריק הראשון, כך שביניהם n − 1 אחדות. זוגי: בכל סבב ה-1 השמאלי הופך ל-x וה-1 הימני ל-Y; כשאין יותר 1, ה-x האחרון הופך לסימן דולר, כל Y הופך ל-1, וכותבים סימן דולר בתא הריק הראשון, כך שביניהם n/2 אחדות.