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

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

איריס ברגורי צור

 

שאלה 1

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

L={0n1n ï n>0}.

פתרון

המכונה תעבוד על פי האלגוריתם הבא:

בכל שלב היא תמחוק 0 שמאלי ביותר ו-1 ימני ביותר.

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

בכל מקרה אחר, המילה אינה בשפה.

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

q0 – מצב התחלתי ומצב תחילת שלב מחיקה חדש, בו המכונה מצפה לראות 0.

q1 – סריקה ימינה עד התא הריק הראשון.

q2 – המכונה מצפה לראות 1 המיועד למחיקה.

q3 – סריקה שמאלה עד התא הריק הראשון.

q4 – הסתיימה קריאת מילת הקלט בהצלחה. מצב מקבל.

המעברים:

מחיקת 0 תורן משמאל –

 

 

אין עוד אותיות קלט. המילה שייכת לשפה –

 

 

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

 

 

מחיקת 1 תורן מימין –

 

 

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

 

שימו לב כי א"ב המכונה הוא ריק.

 

חזרה

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

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