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

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

איריס ברגורי צור ודורון זוהר

 

שאלה 1

לפניך תיאור של מכונות טיורינג בעלת שישה מצבים, כאשר q5 המצב המקבל היחיד. א"ב הקלט הוא {0,1}.

 

א. הראה מסלולי חישוב של המכונה על המילים 101101 ו-1010101.

ב. אילו מילים מתקבלות על ידי המכונה?

ג. מצא דוגמא למילה (שאינה אף אחת מהמילים מסעיף א') עליה המכונה לא עוצרת, וקבע מהי קבוצת כל המילים עליהן המכונה לא עוצרת.

ד. תקן את המכונה כך שתעצור תמיד.

 

פתרון

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

 

 

ניתן לראות שמכונה זו מבצעת סריקה אחת של הקלט וזוכרת תוך כדי הסריקה, בעזרת המצבים, איפיונים של הקלט שקראה. עם סיום קריאת המילה (כלומר קריאת  Δ ראשון) היא מקבלת החלטה – לקבל (לעבור ל-q5) או לדחות (לעבור ל-q4). הקלט עצמו כלל לא משתנה תוך כדי הסריקה, ולכן בעצם מכונה זו עוברת כמו אוטומט סופי.

אלו תפקידי המצבים:

q0 – מצב התחלתי.

q1 – זוכר שקטע הקלט שנקרא עד כה מייצג מספר בינארי (בבסיס 2) המתחלק ב-3.

q2 – זוכר שקטע הקלט שנקרא עד כה מייצג מספר בינארי שחלוקתו ב-3 משאירה שארית 1.

q3 – זוכר שקטע הקלט שנקרא עד כה מייצג מספר בינארי שחלוקתו ב-3 משאירה שארית 2.

q4 – הסתיימה קריאת הקלט ונקרא מספר בינארי שאינו מתחלק ב-3.

q5 – הסתיימה קריאת הקלט ונקרא מספר בינארי המחלק ב-3.

 

א. לא נתאר מסלולי חישוב מלאים. מאחר שהמכונה אינה משנה את הקלט מספיק לומר שעבור המילה הראשונה – 101101 – היא עוצרת במצב המקבל  q5 ועבור המילה השניה היא נכנסת ללולאה אינסופית ב-q4 ולכן דוחה את המילה.

ב. המכונה מקבלת את כל המילים שמייצגות מספר בינארי המתחלק ב-3.

ג. דוגמה נוספת למילה שהמכונה אינה עוצרת עליה: 10. המכונה אינה עוצרת על מילים המייצגות מספר בינארי שאינו מתחלק ב-3.

ד. ניתן לבטל את המצב q4 וכל המעברים אליו, או לבטל את הלולאה העצמית במצב q4 .

 

חזרה

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

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