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

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

ויקטוריה צורי

 

שאלה 1

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

שהן מהצורה wew1 כאשר w היא מילה מעל הא"ב {a,b,c} ו- w1 מתקבלת מ- w על ידי השמטת כל האותיות a מ-w.

למשל, המילים abbcebbc, bbaacebbc, e, aae ו-beb  שייכות לשפה.

 

פתרון

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

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

למכונה שמונה מצבים:

q0 – מצב התחלתי ומצב תחילת שלב סימון חדש, בו המכונה מחפשת אות חדשה לטיפול.

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

q2 – סומנה c בחלקה השמאלי של המילה.

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

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

q5 – חזרה שמאלה בתום שלב הסימון.

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

q7 – מצב מקבל.

א"ב המכונה הוא X,Y}} (ניתן להסתפק גם באות אחת X ולסמן בעזרתה בשני חלקי המילה).

המעברים:

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

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

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

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

סומנה c בחלק השמאלי, יש לחפש c בחלק הימני –

(ימין ,(q0, c, q2, X

סריקה עד חלקה הימני של המילה

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

(ימין ,(q1, a , q1, a

 

(ימין ,(q1, b, q1, b

 

(ימין ,(q1, c, q1, c

סריקה עד חלקה הימני של המילה

כאשר האות האחרונה שסומנה בחלק השמאלי היא c

(ימין ,(q2, a, q2, a

 

(ימין ,(q2, b, q2, b

 

(ימין ,(q2, c, q2, c

המכונה נכנסה לחלק הימני ומחפשת b לסימון –

(ימין ,(q1, e, q3, e

המכונה נכנסה לחלק הימני ומחפשת c לסימון –

(ימין ,(q2, e, q4, e

דילוג על אותיות מסומנות בחלק הימני –

(ימין ,(q3, Y, q3, Y

 

(ימין ,(q4, Y, q4, Y

סימון מוצלח ופניה לכיוון תחילת השלב הבא –

(שמאל ,(q3, b, q5, Y

 

(שמאל ,(q4, c, q5, Y

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

(שמאל ,(q5, Y, q5, Y

 

(שמאל ,(q5, e, q5, e

 

(שמאל ,(q5, a, q5, a

 

(שמאל ,(q5, b, q5, b

 

(שמאל ,(q5, c, q5, c

תחילת שלב סימון חדש –

(ימין ,(q5, X, q0, X

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

(ימין ,(q0, e, q6, e

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

(ימין ,(q6, Y, q6, Y

סיום מוצלח –

(ימין  (q6, Δ, q7,

 

חזרה

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

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