דילוג לתוכן המרכזי

סיכום נושא בחירה: מודלים חישוביים

מדעי המחשב לבגרות · 6 נושאים

כל מה שצריך לדעת בנושא בחירה: מודלים חישוביים: המושגים, הכללים, דרכי פתרון וקוד ב-Java וב-C# עם דוגמאות פתורות משאלוני הבגרות. לחזרה מהירה לפני הבחינה - הסיכום המקוצר או דף כללים.

מודלים חישוביים

בנושא הזה כמעט לא כותבים קוד. מתארים "מכונות" פשוטות שקוראות מילה אות אחר אות ומחליטות אם לקבל אותה, ובודקים מה כל מכונה מסוגלת לעשות ומה לא.
במדויק: הנושא בנוי משלושה מודלים: אוטומט סופי (דטרמיניסטי, דטרמיניסטי לא מלא ולא דטרמיניסטי) ומשפחת השפות הרגולריות; אוטומט מחסנית דטרמיניסטי; ומכונת טיורינג, מודל לתכנית מחשב. בשאלון 899271 אלה שאלות 7-9 (בקיץ 2024: 9-11). שואלים בהן: אם מילה שייכת לשפה, אם שפה רגולרית ולמה, פעולות על שפות, בנייה או השלמה של אוטומט סופי ושל אוטומט מחסנית דטרמיניסטי, ומעקב אחר מכונת טיורינג או בנייה שלה.

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

הכוח של כל מודל

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

1. תיאור מערכות ואוטומט סופי דטרמיניסטי

אוטומט סופי דטרמיניסטי

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

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

טבלת מעברים

בטבלת מעברים יש שורה לכל מצב ועמודה לכל אות. בתא כותבים את המצב שעוברים אליו. מסמנים בחץ → את מצב ההתחלה, וליד כל מצב מקבל כותבים "(מקבל)". כדאי להוסיף עמודה של משמעות המצב.
דוגמה: המילים מעל {a, b} שיש בהן מספר זוגי של a.

מצבמשמעותab
→ q0 (מקבל)נקרא מספר זוגי של aq1q0
q1נקרא מספר אי-זוגי של aq0q1

המילה 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)
דרך הפתרון

בניית אוטומט: מה כל מצב זוכר

1.מבינים את השפה: כותבים 2-3 מילים שבשפה ו-2-3 שלא, וגם בודקים את המילה הריקה ε.
2.מה צריך לזכור בזמן הקריאה כדי להחליט בסוף: שארית, האות האחרונה, הבלוק הנוכחי, מונה עד חסם. אם צריך לזכור מספר בלי חסם, אין אוטומט סופי: השפה לא רגולרית.
3.מצב לכל אפשרות של מה שזוכרים, עם שם שאומר את המשמעות (A1 = "בבלוק ה-a הראשון, שארית 1").
4.מעברים: לכל מצב ולכל אות, מה הזיכרון החדש. מעבר שאחריו המילה בוודאות לא בשפה הולך למצב מלכודת, או לא נכתב כלל אם מותר אוטומט לא מלא.
5.מצבים מקבלים: המצבים שבהם המילה שנקראה עד עכשיו בשפה. אם ε בשפה, מצב ההתחלה מקבל.
6.בדיקה: מריצים את המילים מהשאלה ומצעד 1, וכותבים את המסלול של כל אחת.
שים לב

בודקים תמיד את המילה הריקה ε. בשפה של 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.

פתרון
1.(1) שני תנאים לכל מילה:
מילהרצף ab או bc?מספר ה-a וה-cשייכת?
aacccלא2 + 3 = 5, אי-זוגילא
aabכן, ab2לא
εלא0, זוגיכן
baaלא2, זוגיכן
cbbbaלא1 + 1 = 2, זוגיכן
2.(2) מה לזכור: את הזוגיות של מספר ה-a וה-c (כל a או c מחליף אותה, b לא), ואת האות האחרונה: אחרי a אסור b, אחרי b אסור c, ואחרי c או בהתחלה אין איסור. 2 × 3 = 6 מצבים.
3.הטבלה ("–" = אין מעבר, המילה נדחית):
מצבמשמעותabc
→ q0 (מקבל)זוגי; התחלה או האות האחרונה cq3q4q1
q1אי-זוגי; האות האחרונה cq2q5q0
q2 (מקבל)זוגי; האות האחרונה aq3–q1
q3אי-זוגי; האות האחרונה aq2–q0
q4 (מקבל)זוגי; האות האחרונה bq3q4–
q5אי-זוגי; האות האחרונה bq2q5–
4.בדיקה: cba: q0 → q1 → q5 → q2, מקבל. cbbba: q0 → q1 → q5 → q5 → q5 → q2, מקבל. aab: q0 → q3 → q2, ומ-q2 אין מעבר ב-b, נדחית. aaccc: q0 → q3 → q2 → q1 → q0 → q1, ו-q1 לא מקבל, נדחית. ε: נשארים ב-q0, מקבל.
תשובה

(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 · Bxy, כש-x מ-A ו-y מ-B{ab, abb}
חזקהLⁿשרשור של n מילים מ-L; L⁰ = {ε}A² = {aa, aab, aba, abab}
היפוךR(L) או Lᴿההיפוך של כל מילה ב-LR(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} מול ∅
דרך הפתרון

טענה על שפות: נכונה או לא נכונה

1.מנסים שפות זעירות: {a} ו-{b}, ולפעמים {ab}, ∅ או {ε}. מחשבים את שני האגפים.
2.יצא שונה? זו דוגמה נגדית. כותבים את השפות שבחרתם ואת מה שיצא בכל אגף.
3.נראה שתמיד שווה? מוכיחים הכלה בשני הכיוונים: לוקחים מילה w באגף שמאל ומראים שהיא באגף ימין, ולהפך. במילה משרשור כותבים w = xy, עם x מהשפה הראשונה ו-y מהשנייה.
4.טענה על רגולריות ("אם L₁ ו-L₂ לא רגולריות, אז..."): מחפשים דוגמה נגדית שבה התוצאה היא ∅, {ε} או שפה סופית, שהן רגולריות.
דרך הפתרון

האם מילה שייכת לשפה

1.הצורה: מפרקים את המילה לפי ההגדרה (בלוק a, בלוק b...). אם הסדר לא מתאים, או שחסר בלוק שחייב להיות לא ריק, היא לא שייכת.
2.הפרמטרים: טבלה עם עמודה לכל פרמטר (n, m, k).
3.התנאים: בודקים כל תנאי, רק במקרה שבו הוא כתוב.
4.מסקנה לכל מילה, עם התנאי שהתקיים או שנכשל.
שים לב

אל תבלבלו בין ∅ ל-{ε}. שרשור עם ∅ נותן ∅, ושרשור עם {ε} משאיר את השפה כמו שהיא. ב-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₅

פתרון
1.(1) חיתוך: מחפשים מילים שמופיעות בשתי השפות. ε, 00 ו-001 אינן ב-L₆; 110 נמצאת בשתיהן. התוצאה {110}.
2.(2) היפוך של Σ*: ההיפוך של כל מילה מעל {0, 1} הוא מילה מעל {0, 1}, וכל מילה u היא ההיפוך של uᴿ. לכן מתקבלות שוב כל המילים: Σ*.
3.(3) שרשור עם ∅: אין ב-L₁ אף מילה x, ולכן אין אף זוג xy. התוצאה ∅.
4.(4) שרשור עם {ε}: ε · 0110 = 0110. התוצאה {0110}, כלומר L₄.
5.(5) שרשור: 0110 עם כל מילה של L₅:
מילה מ-L₅השרשור
ε0110
1100110110
00011000
0010110001
תשובה

(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₃)

פתרון
1.(1) ההיפוך הופך את הסדר: R(R(L₁) · R(L₂)) = L₂ · L₁. דוגמה נגדית: L₁ = {a}, L₂ = {b}. באגף שמאל R({a}·{b}) = R({ab}) = {ba}; באגף ימין {ab}. השפות שונות.
2.(2) הכלה בשני הכיוונים.
•תהי w באגף שמאל: w = xy, x מ-L₁, ו-y מ-L₂ או מ-L₃. אם y מ-L₂, w ב-L₁·L₂; אם y מ-L₃, w ב-L₁·L₃. בכל מקרה w באגף ימין.
•תהי w באגף ימין, למשל ב-L₁·L₂: w = xy עם x מ-L₁ ו-y מ-L₂, ולכן y גם ב-L₂ ∪ L₃, ו-w באגף שמאל. אותו דבר ל-L₁·L₃.
3.(3) דוגמה נגדית: L₁ = {ab}, L₂ = {a}, L₃ = {b}. באגף שמאל L₂·L₃ = {ab}, והחיתוך עם L₁ הוא {ab}. באגף ימין L₁ ∩ L₂ = ∅ ו-L₁ ∩ L₃ = ∅, ושרשור עם ∅ הוא ∅. {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)
דרך הפתרון

נימוק: רגולרית או לא

1.מפשטים: אם השפה היא צירוף של שפות, מחשבים מה יוצא. לא פעם יוצא ∅ (אין מילה משותפת), Σ* או שפה סופית, ושלושתן רגולריות.
2.סופית? אם כל הכמויות חסומות, יש מספר סופי של מילים, ולכן השפה רגולרית.
3.מה צריך לזכור? אם מידע חסום מספיק (שארית, מונה עד קבוע, השלב במילה), השפה רגולרית. מתארים במשפט מה המצבים זוכרים.
4.השוואה בין כמויות לא חסומות: לא רגולרית. "כדי לבדוק ש... האוטומט צריך לזכור את n, ו-n לא חסום, ולכן צריך אינסוף מצבים."
5.צירוף שיש בו שפה לא רגולרית: הנחה בשלילה. מניחים שהשפה רגולרית, ומצרפים אליה שפה רגולרית (חיתוך עם a*bc*, איחוד עם שפה סופית) כך שיוצאת שפה שכבר ידוע שאינה רגולרית. זו סתירה.
שים לב

מה שקובע הוא אם הכמות חסומה, לא אם מופיע 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}
בנוגע לכל אחת מהשפות, כתבו אם היא רגולרית או לא. נמקו את תשובתכם (די בהסבר מילולי; אין צורך באוטומט).

פתרון
1.מה חסום בכל שפה:
שפהnkצריך להשוות
L₁חסום (קטן מ-1000)לא חסוםאת מספר ה-c ל-n החסום
L₂לא חסום (גדול מ-1000)חסוםאת מספר ה-c ל-n הלא חסום
L₃חסום (קטן מ-2000)חסוםהכול חסום
2.L₁ רגולרית: האוטומט סופר את ה-a במצבים (עד 999), בודק שיש יותר מ-1000 b (סופר עד 1001 ואחר כך לולאה), ובודק שמספר ה-c שווה ל-n שזכר. k לא חסום, אבל רק צריך להיות גדול מ-1000, ולא משווים אותו לשום דבר.
3.L₂ לא רגולרית: n לא חסום, והאוטומט צריך לבדוק שמספר ה-c שווה בדיוק למספר ה-a. כדי לזכור כל n צריך אינסוף מצבים.
4.L₃ רגולרית: גם n וגם k חסומים, ולכן יש בשפה מספר סופי של מילים. כל שפה סופית רגולרית.
תשובה

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₆, כתבו אם היא רגולרית או לא, ונמקו (די בהסבר מילולי).

פתרון
1.L₄, מפשטים: כל מילה ב-L₂ מתחילה ב-a, וכל מילה ב-R(L₂) (המילים cⁿbᵏaⁿ) מתחילה ב-c. אין מילה משותפת: L₄ = ∅, והשפה הריקה רגולרית.
2.L₅, הנחה בשלילה: נניח ש-L₅ רגולרית. אז גם החיתוך שלה עם השפה הרגולרית a*bc* (בדיוק b אחד) רגולרי. ב-L₁ יש יותר מ-1000 b, ולכן החיתוך הוא {aⁿbcⁿ | n > 1000}, שאינה רגולרית מאותה סיבה כמו L₂. סתירה.
3.L₆, מפשטים: לפי כללי דה מורגן, L̅₁ ∪ L̅₃ הוא המשלים של L₁ ∩ L₃. ב-L₁ יש יותר מ-1000 b וב-L₃ פחות מ-1000, ולכן L₁ ∩ L₃ = ∅, ו-L₆ = Σ*: כל המילים מעל {a, b, c}. זו שפה רגולרית (מצב מקבל אחד עם לולאה על כל האותיות).
תשובה

L₄ = ∅, רגולרית; L₅ לא רגולרית; L₆ = Σ* (כל המילים), רגולרית.

4. מודלים נוספים: אוטומט לא מלא ואוטומט לא דטרמיניסטי

אוטומט לא מלא ואוטומט לא דטרמיניסטי

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

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

מלא, לא מלא, לא דטרמיניסטי

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

השלמת אוטומט נתון

1.מה כל מצב זוכר: מתחילים מהמעברים המסומנים ומהדוגמאות שבשאלה, ומסיקים משמעות לכל מצב ("בבלוק ה-b; מספר ה-a אי-זוגי, מספר ה-b זוגי").
2.תווית לכל מעבר חסר: האות שמעבירה מהמשמעות של מצב המקור למשמעות של מצב היעד. בודקים שלא יצאו שני מעברים באותה אות מאותו מצב.
3.מצבים מקבלים: המצבים שבהם המילה שנקראה עד עכשיו בשפה.
4.בדיקה: מריצים את המילים מהשאלה, גם את אלה שבשפה וגם את אלה שלא.
שים לב

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

שים לב

כשמבקשים אוטומט שאינו מלא, לא צריך מצב מלכודת: מעבר שאחריו המילה בוודאות לא בשפה פשוט לא כותבים. ב-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.

•מעברים עם תווית: q0 → q1 (a), q1 → q2 (a), q1 → q3 (b), q2 → q5 (b), q5 → q7 (c).
•מעברים בלי תווית: q2 → q1, q3 → q4, q4 → q3, q3 → q10, q4 → q8, q5 → q6, q6 → q5, q6 → q10, q7 → q8, q8 → q9, q9 → q8, ולולאה q10 → q10.
•המצבים המקבלים לא סומנו.

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

פתרון
1.מה כל מצב זוכר:
•q1 / q2: בבלוק ה-a, מספר ה-a אי-זוגי / זוגי. לכן q2 → q1 ב-a.
•q3 / q4: אחרי מספר אי-זוגי של a, בבלוק ה-b, מספר ה-b אי-זוגי / זוגי. ב-q3 התנאי על b כבר מתקיים.
•q5 / q6: אחרי מספר זוגי של a, בבלוק ה-b, מספר ה-b אי-זוגי / זוגי. ב-q6 התנאי על b מתקיים.
•q10: התנאי על b התקיים, ולכן כל מספר חיובי של c מתקבל.
•q7, q8, q9: התנאי על b לא התקיים, ולכן צריך שזוגיות מספר ה-c תתאים לזוגיות מספר ה-a. q8 = "מתאים", q7 ו-q9 = "לא מתאים". מ-q4 (a אי-זוגי) c ראשון כבר מתאים, ולכן q4 → q8. מ-q5 (a זוגי) c ראשון לא מתאים (q7), ו-c שני מתאים (q8).
2.הטבלה (בהדגשה: התוויות שהוספנו; "–" = אין מעבר):
מצבabcמקבל?
→ q0q1––לא
q1q2q3–לא
q2q1q5–לא
q3–q4q10לא
q4–q3q8לא
q5–q6q7לא
q6–q5q10לא
q7––q8לא
q8––q9כן
q9––q8לא
q10––q10כן
3.בדיקה: abbbbccc: q0 → q1 → q3 → q4 → q3 → q4 → q8 → q9 → q8, מקבל. aaaabbc: q0 → q1 → q2 → q1 → q2 → q5 → q6 → q10, מקבל. aabc: q0 → q1 → q2 → q5 → q7, לא מקבל.
תשובה

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, שולפים על כל baⁿbⁿ
סכום: מספר ה-b ועוד מספר ה-c שווה למספר ה-aדוחפים על כל a, שולפים על כל b ועל כל caⁱbʲcⁱ⁻ʲ (2025)
משקל: 3 לכל ab ו-1 לכל cדוחפים 3 סימנים על כל ab ואחד על כל c, שולפים על כל b(ab)ᵏcᵐbᵐ⁺³ᵏ (2024)
חצי: n = m/2 + kb ראשון בכל זוג ללא שינוי, b שני שולף; כל c שולף2026
מונה חסום ("לפחות 3 c") או זוגיותסופרים במצבים, לא במחסנית2025, 2026
לדעת מתי המחסנית מתרוקנתהסימן הראשון שנדחף מיוחד (X, Y או S). המעבר ששולף אותו עובר למצב המקבל2024, 2025, 2026
דרך הפתרון

בניית אוטומט מחסנית דטרמיניסטי

1.משוואת הספירה: כותבים את התנאי כשוויון בין מה שנדחף למה שנשלף ("מספר ה-b ועוד מספר ה-c שווה למספר ה-a").
2.דחיפה ושליפה: קובעים כמה סימנים כל אות דוחפת או שולפת.
3.הסימן הראשון מיוחד: האות הראשונה דוחפת סימן אחר (X), וכל השאר דוחפות A. האות ששולפת את X היא האחרונה: עוברים איתה למצב מקבל שאין ממנו מעברים.
4.הסדר והתנאים החסומים, במצבים: מצב לכל בלוק (קוראים a, קוראים b...), ומצבים נוספים לספירה חסומה ("c שני", "c שלישי ומעלה") או לזוגיות.
5.מצבים מקבלים, וגם ε: אם המילה הריקה בשפה, מצב ההתחלה מקבל.
6.דטרמיניזם: בודקים שלכל מצב, אות וראש מחסנית יש לכל היותר מעבר אחד.
7.מעקב: טבלה עם העמודות "נקרא", "מצב", "מחסנית", על מילה מהשפה ועל מילה שנדחית.
שים לב

בשפה של 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.

פתרון
1.משוואת הספירה: מספר ה-c הוא i − j, כלומר מספר ה-b ועוד מספר ה-c שווה למספר ה-a. דוחפים סימן על כל a, ושולפים על כל b ועל כל c. המילה תקינה אם המחסנית מתרוקנת בדיוק עם ה-c האחרון.
2.הסימן הראשון: ה-a הראשון דוחף X, ושאר ה-a דוחפים A. ה-c ששולף את X הוא האחרון: עוברים איתו למצב המקבל f, שאין ממנו מעברים. b לא שולף X (אז j ≥ i, ולא נשאר מקום ל-c).
3.התנאים החסומים: בשפה אין דרישה ש-j > 0. אם יש b, התנאי i − j ≥ 3 כבר נותן i ≥ 4, ולכן צריך לפחות 3 c. אם אין b, צריך i ≥ 4, כלומר לפחות 4 c. סופרים את ה-c במצבים: p1-p4 בלי b, r1-r3 אחרי b.
4.הטבלה. מצב התחלה q0, מצב מקבל f. צירוף שאינו בטבלה = דחייה.
מצבאותראש המחסניתפעולהמצב חדשהסבר
q0aריקהדחוף Xqaה-a הראשון
qaaXדחוף Aqaעוד a
qaaAדחוף Aqaעוד a
qabAשלוףqbb ראשון
qbbAשלוףqbעוד b
qacAשלוףp1c ראשון, אין b
p1cAשלוףp2c שני
p2cAשלוףp3c שלישי
p3cAשלוףp4c רביעי ומעלה
p4cAשלוףp4
p3cXשלוףfc רביעי והאחרון
p4cXשלוףfc אחרון (חמישי ומעלה)
qbcAשלוףr1c ראשון אחרי b
r1cAשלוףr2c שני
r2cAשלוףr3c שלישי ומעלה
r3cAשלוףr3
r2cXשלוףfc שלישי והאחרון
r3cXשלוףfc אחרון (רביעי ומעלה)
5.דטרמיניזם: לכל מצב, אות וראש מחסנית יש לכל היותר שורה אחת.
6.מעקב על aaaabccc (i = 4, j = 1, i − j = 3):
נקראמצבמחסנית (הראש מימין)
התחלהq0ריקה
aqaX
aqaXA
aqaXAA
aqaXAAA
bqbXAA
cr1XA
cr2X
cfריקה

סוף הקלט במצב 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ᵏ}, כאשר:

•אם n%2 = 0: m%2 = 0, n = m/2 + k, וגם n, m, k > 0.
•אם n%2 = 1: n ≤ m + k − 2.

לפניכם אוטומט מחסנית דטרמיניסטי המקבל את L. מצב ההתחלה q0. המעברים בין q0 ל-q1 נתונים במלואם:

•q0 → q1: "a, מחסנית ריקה / דחוף S" וגם "a, A / דחוף A".
•q1 → q0: "a, S / דחוף A" וגם "a, A / דחוף A".

בשאר המעברים מופיעה רק האות:

מעברמ- → אלאות
1-3q0 → q2, q2 → q3, q3 → q2b
4-7q3 → q6, לולאה ב-q6, q3 → q9, q6 → q9c
8-12q1 → 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-21q7 → q10 (b), q7 → q11 (c), q8 → q11 (c), לולאה ב-q10 (b), q10 → q11 (c), לולאה ב-q11 (c)b או c

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

פתרון
1.מה המחסנית מכילה: ה-a הראשון דוחף S וכל a נוסף דוחף A. אחרי n אותיות a יש במחסנית n סימנים: S בתחתית ו-n − 1 פעמים A. האוטומט ב-q0 אם n זוגי וב-q1 אם n אי-זוגי. כש-n = 1 הראש הוא S.
2.n זוגי (q2, q3, q6, q9): צריך n = m/2 + k: כל זוג b שולף סימן אחד, וכל c שולף סימן אחד. S נשלף בדיוק ב-c האחרון, וב-q9 המחסנית ריקה. b לא שולף את S: אז לא נשאר מקום ל-k > 0.
3.n אי-זוגי (q4, q5, q7, q8, q10, q11): צריך m + k ≥ n + 2. שתי האותיות הראשונות אחרי ה-a לא נוגעות במחסנית (מעברים 8-12, עם A או S בראש). אחר כך כל אות שולפת A (n − 1 אותיות). האות הבאה רואה S: התנאי התקיים, ועוברים ל-q10 או ל-q11 בלי לשנות. כאן m = 0 או k = 0 מותרים.
מעבראותראש המחסנית / פעולה
1 (q0 → q2)bA / ללא שינוי
2 (q2 → q3)bA / שלוף
3 (q3 → q2)bA / ללא שינוי
4 (q3 → q6)cA / שלוף
5 (לולאה ב-q6)cA / שלוף
6 (q3 → q9)cS / שלוף
7 (q6 → q9)cS / שלוף
8-12b או cA / ללא שינוי, וגם S / ללא שינוי
13 (לולאה ב-q7)bA / שלוף
14 (q7 → q8)cA / שלוף
15 (לולאה ב-q8)cA / שלוף
16-21b או cS / ללא שינוי
4.בדיקה:
מילההמסלול (המחסנית, הראש מימין)תוצאה
aabbcq1 [S], q0 [SA], q2 [SA], q3 [S], q9 [ריקה]מתקבלת
abbcq1 [S], q4 [S], q7 [S], q11 [S]מתקבלת
aaabbcq1 [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:

מצבקוראכותבתזוזהמצב חדש
q0bbRq0
q0aΔRq1
q0ΔΔLq5

טבלת מעקב: שורה לכל שלב, עם המצב ותוכן הסרט; התא שמתחת לראש מסומן בסוגריים מרובעים. המעקב של אותה מכונה על המילה bb:

שלבמצבתא 0תא 1תא 2תא 3
0q0⊣[b]bΔ
1q0⊣b[b]Δ
2q0⊣bb[Δ]
3q5⊣b[b]Δ

טכניקות שחוזרות

טכניקהאיךבבגרות
דילוגלולאה x / x, R עד שמגיעים לסימן אחרq0 מדלג על b (2026)
חזרה לתחילת הסרטזזים שמאלה עד סימן תחילת הסרט, ואז צעד ימינה2025
בדיקת זוגיותשני מצבים שמתחלפים בכל 12025
סימוןמחליפים 1 בסימן אחר (x, Y) כדי לזכור שהוא טופל2025
סבבים בזוגותבכל סבב מוחקים או מסמנים 1 משני הצדדים, עד שצד אחד נגמרהפרש (2024), חצי (2025)
הזזה שמאלהמוחקים אות, חוזרים תא אחד וכותבים אותה שם; מצב נפרד לכל אות שנזכרת2026
דרך הפתרון

מעקב אחר מכונת טיורינג

1.טבלת מעברים מהציור: לכל חץ מצב, קורא, כותב, תזוזה ומצב חדש.
2.שלב 0: הסרט כמו בשאלה, הראש במקום שהשאלה מראה, מצב ההתחלה.
3.שלב לכל מעבר: מוצאים את המעבר של המצב והתו שמתחת לראש, כותבים, מזיזים, מעדכנים מצב. שורה בטבלה לכל שלב.
4.עצירה: כשאין מעבר. כותבים באיזה מצב המכונה עצרה, אם הוא מקבל, ומה נשאר על הסרט.
5.מה המכונה עושה: מנסים עוד 2-3 קלטים, כולל מקרי קצה (בלי a, מספר 0), ומנסחים משפט שנכון לכל קלט.
דרך הפתרון

בניית מכונת טיורינג

1.אלגוריתם במילים: מה עושים בכל סבב, ומתי עוצרים ("בכל סבב הופכים את ה-1 השמאלי ל-x ואת הימני ל-Y").
2.שלב = קבוצת מצבים: בדיקה, חזרה לתחילה, סבב, סיום. לכל מצב שם שמסביר אותו.
3.מעברים: לכל מצב, מה הוא קורא, מה כותב ולאן זז. מוודאים שהסימנים החדשים (x, Y) מטופלים בכל מצב שעלול לפגוש אותם.
4.הפלט: התוצאה צריכה להיות בדיוק בפורמט שנדרש.
5.בדיקה על הקלטים מהשאלה, וגם על מקרה זוגי ואי-זוגי, קטן וגדול.
שים לב

שאלה על "האם המכונה פועלת נכון" בודקת מקרי קצה. במכונת ההפרש של 2024, כשהמספר השני 0 (הסרט 11#), המצב q6 מגיע לתא של סימן תחילת הסרט ואין לו עליו מעבר. המכונה נתקעת ב-q6, שאינו מצב העצירה q7, ולכן היא לא פועלת נכון.

שים לב

הראש מתחיל במקום שהשאלה מראה. ב-2026 הוא מתחיל על האות הראשונה (תא 1), מימין לסימן תחילת הסרט. כשהשאלה לא מראה, בודקים במכונה: ב-2024 אין ל-q0 מעבר על ⊢, ולכן גם שם הראש מתחיל בתא 1.

שים לב

"כתבו מה המכונה עושה" היא שאלה על כל קלט, לא על הדוגמה. ב-2026 התשובה: המכונה מוחקת את ה-a הראשון ומזיזה את כל מה שאחריו תא שמאלה; מילה בלי a לא משתנה; והמכונה מקבלת כל מילה.

דוגמה א - מעקב אחר מכונה שמוחקת את ה-a הראשון

נתונה מכונת טיורינג המקבלת מילים מעל הא"ב {a, b} (R = ימין, L = שמאל). מצב ההתחלה q0, והמצב המקבל q5. בתחילה הראש על התא שמימין לסימן ⊣ (תא 1).

מצבקוראכותבתזוזהמצב חדש
q0bbRq0
q0aΔRq1
q0ΔΔLq5
q1ΔΔRq5
q1bΔLq3
q1aΔLq2
q2ΔaRq4
q3ΔbRq4
q4ΔΔRq1

(1) עקבו אחרי פעולת המכונה בעבור המילה aba. במעקב יש להראות בכל שלב את הסרט, מעל איזה תא נמצא הראש, ובאיזה מצב המכונה.
(2) כתבו בקצרה מה המכונה עושה.

פתרון
1.שלב 0: הסרט ⊣ a b a, הראש בתא 1, מצב q0.
2.המעקב (הראש בסוגריים מרובעים):
שלבמצבתא 0תא 1תא 2תא 3תא 4תא 5
0q0⊣[a]baΔΔ
1q1⊣Δ[b]aΔΔ
2q3⊣[Δ]ΔaΔΔ
3q4⊣b[Δ]aΔΔ
4q1⊣bΔ[a]ΔΔ
5q2⊣b[Δ]ΔΔΔ
6q4⊣ba[Δ]ΔΔ
7q1⊣baΔ[Δ]Δ
8q5⊣baΔΔ[Δ]
3.מה קרה: בשלב 0 ה-a הראשון נמחק. ב-q1 נקרא b: הוא נמחק, הראש חוזר תא שמאלה, ו-q3 כותב שם b. כלומר ה-b זז תא שמאלה. q4 ממשיך ימינה, ואותו דבר קורה ל-a (q2). כש-q1 קורא Δ, סוף המילה, המכונה עוברת ל-q5 ועוצרת.
4.מה המכונה עושה: q0 מדלג על ה-b שבהתחלה, מוחק את ה-a הראשון, ו-q1 עד q4 מזיזים כל אות שאחריו תא שמאלה. בדיקה: a הופכת למילה הריקה, baba הופכת ל-bba, ו-bb לא משתנה.
תשובה

(1) 9 שלבים (0-8); המכונה עוצרת ב-q5, המילה מתקבלת, ועל הסרט נשאר ba.
(2) המכונה מוחקת מהמילה את המופע הראשון של a ומזיזה את האותיות שאחריו תא שמאלה; אם אין a, המילה לא משתנה. המכונה מקבלת כל מילה.

דוגמה ב - בניית מכונה: חצי המספר או המספר פחות 1

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

•אם המספר שהתקבל זוגי, המכונה מחזירה את המספר המקורי חלקי 2.
•אם המספר שהתקבל אי-זוגי, המכונה מחזירה את המספר המקורי פחות 1.

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

6:  ⊢ 1 1 1 1 1 1 Δ Δ ...   ->   ... $ 1 1 1 $
5:  ⊢ 1 1 1 1 1 Δ Δ ...     ->   ... $ 1 1 1 1 $
פתרון
1.אלגוריתם במילים:
•זוגיות: עוברים ימינה על האחדות ומתחלפים בין qE (עד כאן זוגי) ל-qO (אי-זוגי), עד התא הריק.
•אי-זוגי: חוזרים לתחילת הסרט, הופכים את ה-1 הראשון לסימן דולר, הולכים ימינה עד התא הריק וכותבים בו סימן דולר. ביניהם נשארות n − 1 אחדות.
•זוגי: סבבים. בכל סבב ה-1 השמאלי הופך ל-x (נזרק) וה-1 הימני הופך ל-Y (נשמר). כש-e1 מחפש 1 ופוגש Y, כל האחדות טופלו. אז ה-x האחרון הופך לסימן דולר, כל Y הופך ל-1, ובתא הריק הראשון כותבים סימן דולר. ביניהם n/2 אחדות.
2.טבלת המעברים. הראש מתחיל על ⊢ במצב q0 (אם הראש מתחיל על ה-1 הראשון, מתחילים ישר ב-qE), ו-h הוא מצב העצירה. כל רשומה: מצב, קורא / כותב, תזוזה, ואחרי החץ המצב החדש:
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  -> h
3.למה ב-e3 תמיד יש 1: בתחילת כל סבב מספר האחדות שנשארו זוגי וחיובי. אחרי שה-1 השמאלי הפך ל-x, נשאר לפחות 1 אחד, משמאל ל-Y הראשון או לתא הריק.
4.בדיקה (הסרט בסוף כל סבב):
n = 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 אחדות.

כל האתר במבט אחד

קיצורי דרך לכל הכלים, הבגרויות והקורסים

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