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

ממילים ואוטומטים סופיים למחסנית ולמכונת טיורינג

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

איך לומדים כאן?

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

אין מעברי אפסילון בבניות הקורס. כל מעבר של DFA/NFA או PDA צורך סימן קלט אחד. המילה הריקה ε עדיין יכולה להשתייך לשפה: מקבלים אותה באמצעות מצב התחלתי מקבל, בלי לבצע מעבר. במכונת טיורינג Δ הוא סימן תא ריק שקוראים בפועל, ואינו ε.

מסלול הלמידה

שיעור מה נדע לעשות בסיומו?
01 — מילים ושפות לקרוא הגדרה, לבדוק שייכות ולמצוא את כל המילים הקצרות
02 — קריאת DFA לעקוב אחר תרשים וטבלה ולהגדיר את השפה המתקבלת
03 — בניית DFA לזכור תחילית, סיומת, חפיפות וכמות חסומה
04 — שילוב זיכרון סופי לשלב זוגיות, שארית ותנאים נוספים
05 — DFA לא מלא לבנות מזהה למספרים בינאריים ולהשלים מעברים
06 — NFA ללא אפסילון לעקוב אחרי קבוצת מצבים ולהמיר ל־DFA
07 — פעולות וסגירות לבנות מכפלה ולהוכיח רגולריות באמצעות פעולות
08 — אי־רגולריות להוכיח מגבלות באמצעות קידומות נבדלות וניפוח
09 — חשיבה על שפות לפשט הגדרות, לבדוק הכלה ולמצוא דוגמאות נגדיות
10 — יסודות PDA לעקוב אחרי מחסנית ולבנות השוואת כמויות וסוגריים
11 — בניות PDA לשלב מחסנית, יחסים, אי־שוויונות ושלבי קלט
12 — גבולות המחסנית לסווג שפות ולנמק גם אי־חופשיות הקשר
13 — יסודות טיורינג לעקוב אחרי סרט ולהסיק איזו פונקציה מכונה מחשבת
14 — חישוב והשוואת מודלים לבנות חישוב אונרי, להוכיח עצירה ולהבחין בין תפקידי מכונות

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

מפת המטלות: מה ללמוד לפני כל סעיף?

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

מטלה 1 — PDF

סעיף נושא שיעורים
1א מתחילה ומסתיימת ב־1 2–3
1ב תחילית 01 וסיומת 10, כולל חפיפה 3
1ג תחילית 01 והופעת 10 3
1ד תחילית 1 ובדיוק שני 2 3
2(1), מילים i–iv מסלולי קבלה ודחייה באוטומט נתון 2
2(2) ניסוח השפה מתוך האוטומט 2
3א כל המילים הקצרות 1
3ב(1–3) שייכות, כולל המילה הריקה 1
3ג דוגמאות נגדיות עם אילוץ אורך 1, 4

מטלה 2 — PDF

סעיף נושא שיעורים
1א תחילית 11, סיומת 1 וזוגיות 4
1ב תחילית והופעה של 11, אורך אי־זוגי 4, 9
1ג אורך מתחלק בשלוש ואי־סיום ב־2 4
1ד הופעת 12, אי־סיום ב־22 וזוגיות 3–4, 7
2א NFA לסיומת bbc 6
2ב הופעת aaa או aba וסיומת b 6
2ג תחילית ab, הופעת abb וסיומת ab או bb 3, 6–7
2ד קשיים בהוראת NFA ודרכי התמודדות 6
3 אוטומט חיתוך, איסור aa ו־aba, סיומת a 7
4 השלמת תרשים לא מלא בלי שינוי מספר מצבים 5, 9

מטלה 3 — PDF

סעיף נושא שיעורים
1א שוויון מספר a בקידומת למספר c בסיומת 8
1ב הוכחת אי־רגולריות של \(a^ib^jcd^k\), עם \(j>k\) 8
2א(1) היפוך \(L_5\) וסיווג \(L_6\) 7, 12
2א(2) \(L_7=\overline{L_3}\cap L_2\) 9
2ב(3) חיתוך ושרשור: \((L_1\cap L_2)L_5\) 7, 9
2ב(4) האם \(L_3\cap L_4\) ריק 9
2ב(5) בדיקת הכלת \(L_2\) ב־\(L_3\) 9
2ג אי־רגולריות כשאותו מונה קושר שני בלוקים 8
2ד רגולריות אחרי הפרדת המונים 8–9
3 הוכחה בעזרת סגירות בלבד 7

מטלה 4 — PDF

סעיף נושא שיעורים
1א המילה הקצרה ב־\(a^nb^{3k+1}c^k\) 1
1ב PDA ליחס שלוש ועוד אחד 10–11
2 PDA דטרמיניסטי ל־\(a^{2n}b^mc^k\), עם \(k>n+m\) 11
3א המילה הקצרה ב־\(a^sb^{2s}(a^+b^+)^+\) 1, 11
3ב השוואה במחסנית ואחריה זנב רגולרי 11
3ג קשיים ודרכי הוראה 10–11
4א, השפות \(L_1\)–\(L_5\) רגולרית, חופשית הקשר, לא חופשית הקשר 8–9, 12
4ב(1) \(L_2\subset L_4\) 9
4ב(2) \(L_3\cap L_4\ne\varnothing\) 9
4ב(3) \(\overline{L_4}\cap L_1\ne\varnothing\) 9

מטלה 5 — PDF

סעיף נושא שיעורים
1א–ג והדוגמאות DFA לא מלא למספרים בינאריים 5
2א המילה הקצרה והגדרת השפה 1, 11
2ב הוכחת אי־רגולריות 8, 11
2ג PDA להשוואת הבלוק הראשון לאחרון 11
3א תרשים מתוך רשימת מעברים 13
3ב מעקב על הקלט 5 13
3ג הפונקציה המחושבת 13
3ד הוספת טיפול באפס 13
4, שני ענפי הפונקציה חצי ממספר זוגי, אחד פחות מאי־זוגי 14
רפלקציה: הוראה בשנה הבאה, התפתחות מקצועית, מיומנויות, שימור ושיפור שאלות אישיות למורים, אינן פרק חובה לתלמידים עזר למורה להלן
עזר למורה — רפלקציה על הוראת הקורס

לא נכתוב תשובות אישיות במקום המורה. אפשר לבסס רפלקציה על תוצרי הלמידה: האם התלמידים מסבירים משמעות של מצב? האם הם בודקים ε וגבולות? האם הם מזהים פתרון עם אפסילון שאינו תואם את הכללים? אילו משימות דרשו תיווך נוסף? מתוך העדויות האלה אפשר לענות על ארבע שאלות הרפלקציה ולתכנן את ההוראה הבאה.

סימון, מקורות ואי־בהירויות

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

  • מצבים: Mermaid מסוג stateDiagram-v2, עם זרימה משמאל לימין, סימון התחלה שאינו מעבר ומסגרת עבה למצבים מקבלים. בכל דוגמה מפורשת גם קבוצת הקבלה או מצב העצירה. תיעוד התחביר הרשמי.
  • מחסנית: סימון המורה עם דחוף, שלוף, ללא שינוי; ⊥ הוא התחתית, ו־S יחידת הספירה הראשונה כשנדרש להבחין בה.
  • מטלה 2: הדרישה “מכילה 11” אחרי “מתחילה ב־11” אינה מחייבת הופעה נוספת; הזוגיות החוזרת בסעיף 1ד היא תנאי אחד.
  • מטלה 3: הקו מעל \(L_3\) בהגדרת \(L_7\) הוא משלים; בכמתים של “מכילה \((ac)^k\)” הקריאה היא שקיים \(k>1\).
  • מטלה 4: הנוסחה בשאלה 3 נקראת \(a^sb^{2s}\) ואחריה לפחות זוג בלוקים לא ריקים. המשתנה \(m\) המיותר בתנאי \(L_3\) אינו משנה את השפה.
  • מטלה 5: ההגדרה והדוגמאות החיוביות בשאלה 2 אינן עקביות. שיעור 11 מציג את הסתירה ואת הפרשנות שנבחרה, במקום להעביר אותה לתלמיד כעובדה.

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

הדפים ההיסטוריים

מתחילים בשיעור 01 — מילים ושפות