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

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

ריקה רם

 

שאלה 1

נתונה מכונת טיורינג הבאה:

א"ב הקלט {a,b,c}. א"ב המכונה ריק. קבוצת המצבים היא {q0,q1,q2}. q0 המצב ההתחלתי. המצב המקבל הוא q2. המכונה עובדת לפי מוסכמת פלט שונה מזו שמקובלת בספר הלימוד: הפלט הוא כל מה שרשום על הסרט עם עצירת המכונה.

א. מהו הפלט של המכונה על מילות הקלט abbc, bbb, aaa?

ב. מה מבצעת המכונה?

ג. שנה את המכונה כך שתמחק כל מילה המסתיימת  ב-a.

 

פתרון

א. על aaa הפלט הוא aaa. על bbb הפלט הוא ccc. על abbc הפלט הוא accb.

ב. מחליפה כל b ב-c וכל c ב-b.

ג. יש להוסיף מצבים נוספים:

   q3 – זוכר כי האות האחרונה שנקראה היא a. q4 – מצב מחיקה.
את המעבר הראשון נבטל ונוסיף את המעברים הבאים:

q4 יהיה גם הוא מצב מקבל.

 

שאלה 2

נתונה מכונת טיורינג הבאה:

א"ב הקלט {a,b}. א"ב המכונה ריק. קבוצת המצבים היא {q0,q1,q2,q3,q4,q5}. המצב ההתחלתי הוא q0 והמצב המקבל הוא q3.

זו קבוצת המעברים:

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

א. לפניכם המילים babb, abaaba, abbaba. קבעו עבור כל מילה אם היא מתקבלת  על ידי המכונה.

ב. מהי השפה שמקבלת המכונה?

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

 

פתרון

א. babb לא מתקבלת (המכונה נכנסת לחישוב אינסופי).
   
abaaba מתקבלת.
   
abbaba לא מתקבלת (המכונה נכנסת לחישוב אינסופי).

ב. המכונה מקבלת את השפה {(aba)n |  n > 0}.

ג. המכונה לא עוצרת על המילה הריקה (בגלל הלולאה ב-q0). המכונה לא עוצרת כאשר היא מוצאת אות שאינה עקבית עם רצף aba תורן (בגלל המעברים ל-q4 והלולאה ב-q4 ובגלל המעבר מ-q3 ל- q5 ומ-q5 ל-q0 תוך כדי חזרה שמאלה ומ-q0 ל-q4 והלולאה ב- (q4.

המכונה עוצרת ולא מקבלת מילים מהצורה (aba)ia או (aba)iab. (i³0).

כדי לקבל אותה שפה ולעצור על כל מילת קלט יש לבטל את q4 והמעברים אליו, את הלולאה ב-q0 ואת q5 והמעברים הנוגעים בו. נישאר עם המכונה הפשוטה הבאה:

 

כמובן, מספיק גם לבטל רק את הלולאות ב-q0 וב-q4.

 

חזרה

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

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