מודלים חישוביים — מטלה מסכמת מס' 5

תמלול השאלות ואזורי עבודה

מטלת הגשה מס’ 5 — מסכמת

קורס: מודלים חישוביים
מורה: צורי ויקטוריה
תאריך אחרון להגשה: 7.07.2026

הנחיות לביצוע המטלה

  • ענו על כל השאלות שלפניכם.
  • הגשת הפתרון היא אישית.
רפלקציה על ההשתלמות

מורים יקרים, יש לצרף לעבודה המסכמת רפלקציה קצרה על הקורס:

  • האם אני מתכוון/ת ללמד את היחידה בשנת הלימודים הבאה?
  • כיצד ההשתלמות תרמה לפיתוח המקצועי שלי?
  • אילו מיומנויות חדשות למדתי בהשתלמות, וכיצד איישם אותן בהוראתי בעתיד?
  • נקודות לשימור או לשיפור באופן העברת ההשתלמות.

אזור כתיבה

NEEDHELP — להשלים כאן את הרפלקציה האישית.

שאלה 1 — אוטומט סופי דטרמיניסטי לא מלא

בנו אוטומט סופי דטרמיניסטי לא מלא המקבל את שפת כל המילים מעל האלפבית

\[\Sigma = \{0,1,\texttt{.}\}\]

המהוות מספרים בינאריים, עם נקודה עשרונית או בלעדיה, כאשר:

  1. אם מופיעה נקודה, חייבת להיות לפחות ספרה אחת לפניה ולפחות ספרה אחת אחריה.
  2. אם מופיעה נקודה, אסור שהמספר יסתיים ב־0 — כלומר, לא תופיע בסופו ספרת 0 חסרת משמעות.
  3. אסור שיופיעו אפסים מובילים.

דוגמאות

מילים השייכות לשפה מילים שאינן שייכות לשפה
0 0.0
10100 00101
0.101 1010.110
0.011  
1001  

אזור עבודה — תרשים האוטומט

flowchart LR
    NEEDHELP_Q1["NEEDHELP — להשלים כאן את תרשים ה-DFA הלא מלא"]

טבלת מעברים

מצב קלט 0 קלט 1 קלט . מצב מקבל?
NEEDHELP        
         
         
         

NEEDHELP — להשלים שמות מצבים, מעברים ומצבים מקבלים.

שאלה 2 — שפה, רגולריות ואוטומט מחסנית

נתונה השפה:

\[L = \left\{ a^{i_1} b a^{i_2} b \dots c a^{i_n} \;\middle|\; n \ge 2; \ \forall k\ (1 \le k \le n),\ i_k \ge 1; \ i_1 = i_n \right\}\]

הסבר לשפה

  • אוסף כל המילים מעל האלפבית ${a,b,c}$ המכילות רצפים של a, כאשר b מפריד בין רצף לרצף.
  • מספר אותיות ה־a ברצף הראשון שווה למספר אותיות ה־a ברצף האחרון.
  • לפני הרצף האחרון מופיע c במקום b.

הערה חשובה: רצף של a חייב להכיל לפחות a אחת.

דוגמאות

מילים השייכות לשפה מילים שאינן שייכות לשפה
abaaca abca
aaabacaaa ababa
  abaacaa

NEEDHELP-CLARIFY — לבדוק אם רוצים לנסח את הביטוי הפורמלי במפורש גם עבור המקרה $n=2$, כדי למנוע עמימות במיקום ה־b וה־c.

סעיפים

א. מהי המילה הקצרה ביותר בשפה? נמקו את קביעתכם.

NEEDHELP — להשלים מילה ונימוק.

ב. האם השפה רגולרית? הוכיחו.

NEEDHELP — להשלים טענה והוכחה.

ג. בנו אוטומט מחסנית לשפה.

טיפ: בדקו את האוטומט שבניתם על המילים שבדוגמה.

אזור עבודה — אוטומט מחסנית

flowchart LR
    NEEDHELP_Q2["NEEDHELP — להשלים כאן את תרשים אוטומט המחסנית"]

טבלת מעברים לאוטומט המחסנית

מצב נוכחי תו קלט ראש המחסנית מצב הבא פעולה במחסנית
NEEDHELP        
         
         
         
שאלה 3 — מכונת טיורינג באונרית

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

לפניכם קבוצת המעברים של המכונה:

מצב נוכחי הסימן הנקרא מצב הבא הסימן הנכתב תנועה
q0 1 q1 x ימין
q1 1 q2 x ימין
q1 Δ q7 $ ימין
q2 1 q3 x ימין
q2 Δ q6 $ ימין
q3 1 q1 x ימין
q3 Δ q4 $ ימין
q4 Δ q5 $ ימין
q6 Δ q7 1 ימין
q7 Δ q4 1 ימין

המצב q5 הוא מצב מקבל.

סעיפים

א. ציירו אוטומט מכונת טיורינג לפי קבוצת המעברים.

flowchart LR
    NEEDHELP_Q3A["NEEDHELP — להשלים כאן את תרשים מכונת הטיורינג"]

ב. בנו מעקב על המספר 5.

צעד מצב תוכן הסרט מיקום הראש המעבר שבוצע
0 q0 11111    
1        
2        
3        
NEEDHELP        

NEEDHELP — להוסיף שורות לפי מספר צעדי החישוב.

ג. הגדירו את הפונקציה שמכונת הטיורינג מבצעת.

NEEDHELP — להשלים את הגדרת הפונקציה בלבד.

ד. היכן מתבטאת העובדה שהמכונה אינה מטפלת במספר 0? הוסיפו את הדרוש.

NEEDHELP — להסביר ולהוסיף מעבר או מעברים נדרשים.

שאלה 4 — מכונת טיורינג המחלקת זוגי ב־2 ומפחיתה 1 מאי־זוגי

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

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

הנחיות

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

דוגמה למספר זוגי

הסרט לפני ההרצה

תא 0 1 2 3 4 5 6 7 8 9 10 11
תוכן ⊢ 1 1 1 1 1 1 Δ Δ Δ Δ Δ

הסרט לאחר ההרצה

תא … 0 1 2 3 4
תוכן … $ 1 1 1 $

דוגמה למספר אי־זוגי

הסרט לפני ההרצה

תא 0 1 2 3 4 5 6 7 8 9 10
תוכן ⊢ 1 1 1 1 1 Δ Δ Δ Δ Δ

הסרט לאחר ההרצה

תא … 0 1 2 3 4 5
תוכן … $ 1 1 1 1 $

אזור עבודה — תרשים המכונה

flowchart LR
    NEEDHELP_Q4["NEEDHELP — להשלים כאן את תרשים מכונת הטיורינג"]

טבלת מעברים

מצב נוכחי הסימן הנקרא מצב הבא הסימן הנכתב תנועה הערה
NEEDHELP          
           
           
           
           

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