מאגר שאלות ותשובות להוראת מודלים חישוביים:

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

אסנת אנגלמן, אסתי מאסטראסי, אורנה אברך-שטיין

 

שאלה 1

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

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

 

פתרון

המכונה שנבנה זוכרת בעזרת בקרת המצבים כמה מספרים זוגיים וכמה מספרים אי-זוגיים ראתה. בהתאם למצב בו היא נמצאת עם סיום קריאת הקלט נכתב הפלט. משום כך יש למכונה זו מצבים רבים. הזיהוי אם מספר הוא זוגי או לא נעשה לפי האות האחרונה (הימנית) שלו: אם היא 0 זה מספר זוגי, ואם היא 1 זה מספר אי-זוגי. א"ב הקלט הוא {0,1,#}. א"ב המכונה הוא {$,X}. למכונה 32 מצבים:

q0 – מצב התחלתי, בו המכונה מחפשת את החוצץ הראשון.

q1 – אחרי זיהוי החוצץ הראשון, לקריאת האות האחרונה של המספר הראשון.

q2 – לחיפוש החוצץ השני כאשר היה מספר אי-זוגי אחד.

q3 – לחיפוש החוצץ השני כאשר היה מספר זוגי אחד.

q4 – אחרי זיהוי החוצץ השני – לקריאת האות האחרונה של המספר השני, כאשר המספר הראשון היה אי-זוגי.

q5 – אחרי זיהוי החוצץ השני – לקריאת האות האחרונה של המספר השלישי, כאשר המספר הראשון היה זוגי.

q6 – לחיפוש החוצץ השלישי כאשר לפני כן היו שני מספרים אי-זוגיים.

q7 – לחיפוש החוצץ השלישי כאשר לפני כן היה מספר אחד זוגי ומספר אחד אי-זוגי.

q8 – לחיפוש החוצץ השלישי כאשר לפני כן היו שני מספרים זוגיים.

q9 – אחרי זיהוי החוצץ השלישי, לקריאת האות האחרונה של המספר השלישי כאשר לפני כן היו שני מספרים אי-זוגיים. 

q10 – אחרי זיהוי החוצץ השלישי, לקריאת האות האחרונה של המספר השלישי, כאשר לפני כן היה מספר אחד זוגי ומספר אחד אי-זוגי.

q11 – אחרי זיהוי החוצץ השלישי, לקריאת האות האחרונה של המספר השלישי, כאשר לפני כן היו שני מספרים זוגיים.

q12 – לחיפוש סוף הקלט כאשר לפני כן היו שלושה מספרים אי-זוגיים.

q13 – לחיפוש סוף הקלט כאשר לפני כן היו שני מספרים אי-זוגיים ומספר אחד זוגי.

q14 – לחיפוש סוף הקלט כאשר לפני כן היו מספר אחד אי-זוגי ושני מספרים זוגיים.

q15 – לחיפוש סוף הקלט כאשר לפני כן היו שלושה מספרים זוגיים.

q16 – אחרי זיהוי סוף הקלט, לקריאת האות האחרונה של המספר הרביעי, כאשר לפני כן היו שלושה מספרים אי-זוגיים.

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

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

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

q20 – לחיפוש סוף הקלט כאשר לפני כן היו ארבעה מספרים אי-זוגיים.

q21 – לחיפוש סוף הקלט כאשר לפני כן היו שלושה מספרים אי-זוגיים ומספר אחד זוגי.

q22 – לחיפוש סוף הקלט כאשר לפני כן היו שני מספרים אי-זוגיים ושניים זוגיים.

q23 – לחיפוש סוף הקלט כאשר לפני כן היו מספר אחד אי-זוגי ושלושה זוגיים.

q24 – לחיפוש סוף הקלט כאשר לפני כן היו ארבעה מספרים זוגיים.

q25 – נכתב $ ראשון וכעת יש לכתוב $ שני.

q26 – נכתב $ ראשון וכעת יש לכתוב עוד 1.

q27 – נכתב $ ראשון וכעת יש לכתוב 10.

q28 – נכתוב $ ראשון וכעת יש לכתוב 11.

q29 – נכתב $ ראשון וכעת יש לכתוב 100.

q30 – נכתב $ ראשון וכעת יש לכתוב 00.

q31 – נכתב $ ראשון וכעת יש עוד לכתוב 0.

q32 – מצב מקבל.

אלו המעברים:

חיפוש חוצץ ראשון –

(ימין ,(q0, 0, q0, 0

 

(ימין ,(q0, 1, q0, 1

מציאת חוצץ ראשון –

(שמאל ,X (q0, #, q1,

מספר ראשון אי-זוגי –

(ימין ,1 (q1, 1, q2,

מספר ראשון זוגי –

(ימין ,0 (q1, 0, q3,

חיפוש חוצץ שני –

(ימין ,(q2, 0, q2, 0

 

(ימין ,(q2, 1, q2, 1

 

(ימין ,X (q2, X, q2,

 

(ימין ,0 (q3, 0, q3,

 

(ימין ,1 (q3, 1, q3,

 

(ימין ,X (q3, X, q3,

מציאת חוצץ שני –

(שמאל ,X (q2, #, q4,

 

(שמאל ,X (q3, #, q5,

שני מספרים אי-זוגיים –

(ימין ,1 (q4, 1, q6,

מספר אחד זוגי ואחד אי-זוגי –

(ימין ,0 (q4, 0, q7,

 

(ימין ,1 (q5, 1, q7,

שני מספרים זוגיים –

(ימין ,0 (q5, 0, q8,

חיפוש חוצץ שלישי –

(ימין ,(q6, 0, q6, 0

 

(ימין ,(q6, 1, q6, 1

 

(ימין ,X (q6, X, q6,

 

(ימין ,0 (q7, 0, q7,

 

(ימין ,1 (q7, 1, q7,

 

(ימין ,X (q7, X, q7,

 

(ימין ,0 (q8, 0, q8,

 

(ימין ,1 (q8, 1, q8,

 

(ימין ,X (q8, X, q8,

מציאת חוצץ שלישי –

(שמאל ,X (q6, #, q9,

 

(שמאל ,X (q7, #, q10,

 

(שמאל ,X (q8, #, q11,

שלושה אי-זוגיים –

(ימין ,1 (q9, 1, q12,

שני אי-זוגיים וזוגי –

(ימין ,0 (q9, 0, q13,

 

(ימין ,1 (q10, 1, q13,

שני זוגיים ואי-זוגי –

(ימין ,0 (q10, 0, q14,

 

(ימין ,1 (q11, 1, q14,

שלושה זוגיים –

(ימין ,0 (q11, 0, q15,

חיפוש סוף הקלט –

(ימין ,0 (q12, 0, q12 ,

 

 

(ימין ,X (q12, X, q12 ,

 

(ימין ,0 (q13, 0, q13 ,

 

(ימין ,1 (q13, 1, q13 ,

 

(ימין ,X (q13, X, q13 ,

 

(ימין ,0 (q14, 0, q14,

 

(ימין ,1 (q14, 1, q14,

 

(ימין ,X (q14, X, q14,

 

(ימין ,0 (q15, 0, q15,

 

(ימין ,1 (q15, 1, q15,

 

(ימין ,X (q15, X, q15,

מציאת סוף קלט –

 

 

 

ארבעה אי-זוגיים –

(ימין ,1 (q16, 1, q20,

שלושה אי-זוגיים וזוגי אחד –

(ימין ,0 (q16, 0, q21,

 

(ימין ,1 (q17, 1, q21,

שני אי-זוגיים ו-שני זוגיים –

(ימין ,0 (q17, 0, q22,

 

(ימין ,1 (q18, 1, q22,

אי-זוגי אחד ו-שלושה זוגיים –

(ימין ,0 (q18, 0, q23,

 

(ימין ,1 (q19, 1, q23,

ארבעה זוגיים –

(ימין ,0 (q19, 0, q24,

נכתב $ ראשון.

היו ארבעה אי זוגיים ולכן צריך לכתוב רק עוד $ אחד –

(ימין ,$ (q20, Δ, q25,

נכתב $ ראשון. היה זוגי אחד ולכן צריך לכתוב עוד 1 ואז $ –

(ימין ,$ (q21, Δ, q26,

נכתב $ ראשון. היו שני זוגיים ולכן צריך לכתוב עוד 10 ואז $ –

(ימין ,$ (q22, Δ, q27,

נכתב $ ראשון. היו שלושה זוגיים ולכן צריך לכתוב עוד 11 ואז $ –

(ימין ,$ (q23, Δ, q28,

נכתב $ ראשון. היו ארבעה זוגיים ולכן צריך לכתוב עוד 100 ואז $ –

(ימין ,$ (q24, Δ, q29,

סיום מילת הפלט –

(ימין ,$ (q25, Δ, q32,

נכתב 1 ונותר לכתוב עוד $ –

(ימין ,1 (q26, Δ, q25,

נכתב 1 ונותר לכתוב עוד 0 ו-$ –

(ימין ,1 (q27, Δ, q31,

נכתב 1 ונותר לכתוב עוד 1 ו-$ –

(ימין ,1 (q28, Δ, q26,

נכתב 1 ונותר לכתוב עוד 00 ו-$ –

(ימין ,1 (q29, Δ, q30,

נכתב 0 ונותר לכתוב עוד 0 ו-$ –

(ימין ,0 (q30, Δ, q31,

נכתב 0 ונותר עוד $ לכתוב –

(ימין ,0 (q31, Δ, q25,

 

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

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

 

שאלה 2

בנה מכונת טיורינג המקבלת מילה בעברית ומזהה אם נכתבה בלשון נקבה (סיומת 'ה' או סיומת 'ות').

פתרון

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

q0 – מצב התחלתי ומצב לסריקת מילת הקלט.

q1 – מצב המזהה את סיום המילה.

q2 – מצב הזוכר סיומת 'ת' ומחפש לפניה 'ו'.

q3 – מצב מקבל.

אלו המעברים:

לכל אות s בא"ב העברי (יש כאן 22 מעברים) –

(ימין ,s (q0, s, q0,

זיהוי סוף מילה –

זיהוי סיומת 'ה' –

(ימין , q3 ,q1)

זיהוי סיומת 'ת' –

(שמאל , q2 ,q1)

זיהוי סיומת 'ות' –

(ימין , q3 ,q2)

 

שאלה 3

בנה מכונת טיורינג המקבלת את השפה הבאה מעל הא"ב {a,b}:

{ w=R(w1) או L={ w×w1 ï w=w1

פתרון

זהו תרגיל לא קל המתאים כעבודת כיתה או בית אך לא למבחן.

המכונה היא מכונה לא דטרמיניסטית המנחשת בצעד הראשון אם מילת הקלט היא מהצורה w×w או w×R(w). בהתאם לניחוש היא ממשיכה לפעול כמו מכונה המקבלת את כל המילים מהצורה w×w או כמו מכונה המקבלת את כל המילים מהצורה w×R(w). ניתן להתייחס לזה כמו אל שתי תת-מכונות (שגרות) שאחת מהן אף היא לא דטרמיניסטית משום שעליה לנחש את נקודת האמצע של המילה.

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

א"ב הקלט הוא כמובן {a,b} וא"ב המכונה הוא {X,Y}. למכונה תשעה מצבים:

p0 – מצב התחלתי, בו המכונה מצפה לראות את האות הראשונה לסימון בחלקה הראשון (השמאלי) של המילה.

p1 – מצב תחילת שלב שני ואילך, בו המכונה מצפה לראות את האות הבאה לסימון בחלקה הראשון של המילה. 

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

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

p4 – מצב בו המכונה מצפה לראות את האות הבאה לסימון בחלק השני של המילה ועליה להיות a.

 p5– מצב בו המכונה מצפה לראות את האות הבאה לסימון בחלק השני של המילה ועליה להיות b.

p6 – סומנה אות בחלקה השני של המילה ויש חזרה אחורה עד לאות הבאה לסימון בחלקה הראשון של המילה.

p7 – מצב סריקה ימינה עם סיום החלק הראשון לוודא שהסתיים גם החלק השני.

p8 – מצב מקבל.

המעברים:

סומנה אות ראשונה בחלק הראשון וזו a

(ימין ,X (p0, a, p2,

סומנה אות ראשונה בחלק הראשון וזו b

(ימין ,X (p0, b, p3,

סריקת החלק הראשון לפני חציית קו האמצע –

(ימין ,a (p2, a, p2,

 

(ימין ,b (p2, b, p2,

 

(ימין ,a (p3, a, p3,

 

(ימין ,b (p3, b, p3,

ניחוש נקודת האמצע –

(שמאל ,Y (p3, a, p6,

 

(שמאל ,Y (p3, b, p6,

סריקה אחורה עד האות הבאה לסימון בחלק הראשון –

(שמאל ,Y (p6, Y, p6,

 

(שמאל ,a (p6, a, p6,

 

(שמאל ,b (p6, b, p6,

 

(ימין ,X (p6, X, p1,

סומנה אות שנייה ויותר בחלק הראשון וזו a

(ימין ,X (p1, a, p4,

סומנה אות שנייה ויותר בחלק הראשון וזו b

(ימין ,X (p1, b, p5,

סריקת החלק הראשון ותחילת החלק השני עד האות הבאה לסימון בחלק השני

(ימין ,a (p4, a, p4,

 

(ימין ,b (p4, b, p4,

 

(ימין ,Y (p4, Y, p4,

 

(ימין ,a (p5, a, p5,

 

(ימין ,b (p5, b, p5,

 

(ימין ,Y (p5, Y, p5,

סומנה אות בחלק השני של המילה –

(שמאל ,Y (p4, a, p6,

 

(שמאל ,Y (p5, b, p6,

סיום החלק הראשון של המילה –

(ימין ,Y (p1, Y, p7,

סריקה ימינה לוודא שהסתיים החלק השני –

(ימין ,Y (p7, Y, p7,

סיום החלק השני –

(ימין ,Δ (p7, Δ, p8,

לקבלת המילה הריקה –

(ימין ,Δ (p0, Δ, p8,

 

ניתן לוותר על המעבר האחרון, אם הופכים את p0 למצב מקבל.

 

המכונה השנייה אמורה כאמור לקבל את כל המילים מהצורה w×R(w). המכונה מסמנת בכל שלב אות תורנית שמאלית ביותר ואות תורנית ימנית ביותר זהה לה. גם א"ב הקלט שלה הוא {a,b} וא"ב המכונה אף הוא {X,Y}. למכונה שישה מצבים:

t0 – מצב התחלתי ומצב תחילת כל שלב.

t1 – בחלק השמאלי סומנה a.

t2 – בחלק השמאלי סומנה b.

t3 – זוהה קצה ימני של החלק הלא מסומן והוא צריך להיות a.

t4 – זוהה קצה ימני של החלק הלא מסומן והוא צריך להיות b.

t5 – חזרה אחורה בסיום שלב.

t6 – מצב מקבל.

אלו המעברים:

קריאת האות הראשונה במילה, a

(ימין, a (t0, a ,t1 ,

קריאת האות הראשונה במילה, b

(ימין, b (t0, b ,t2 ,

זיהוי סיום מוצלח של התהליך

(ימין, Y (t0, Y ,t6 ,

סריקת המילה עד האות האחרונה שעדיין לא סומנה בחלק הימני –

(ימין, a (t1, a ,t1 ,

 

(ימין, b (t1, b ,t2 ,

 

(ימין, b (t2, a ,t1 ,

 

(ימין, b (t2, b ,t2 ,

זיהוי קצה ימני לא מסומן –

(שמאל ,D (t1, D, t3,

 

(שמאל ,D (t2, D, t4,

 

(שמאל ,Y (t1, Y, t3,

 

(שמאל ,Y (t2, Y, t4,

סימון אות תורנית בקצה הימני –

(שמאל ,Y (t3, a, t5,

 

(שמאל ,Y (t4, b, t5,

חזרה אחורה לחיפוש האות הבאה לסימון בחלק הראשון –

(שמאל ,a (t5, a, t5,

 

(שמאל ,b (t5, b, t5,

הכנה לקראת שלב סימון חדש ­–

(ימין ,X (t5, X, t0,

לקבלת המילה הריקה –

(ימין ,Δ (t0, Δ, p6,

 

גם במקרה זה אפשר להפוך את t0 למצב מקבל, ולוותר על המעבר האחרון.

 

כדי ליצור משתי התת-מכונות מכונה אחת, נוסיף מצב התחלתי חדש q0. נוסיף את המעברים הבאים:

ניחוש כי המילה מהצורה w×w

(ימין ,X (q0, a, p2,

 

(ימין ,X (q0, b, p3,

ניחוש כי המילה מהצורה w×R(w)

(ימין ,a (q0, a, t1,

 

(ימין ,b (q0, b, t2,

 

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

ניתן גם לאחד את שני המצבים המקבלים (p8 ו-t9) למצב מקבל אחד, אך אין זה הכרחי.

 

חזרה

למאגר החומרים

לאתר מודלים חישוביים