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

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

לאה יעקובוביץ

 

שאלה 1

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

 

פתרון

השפה המבוקשת היא בדיוק שפת כל המילים מהצורה w×R(w) מעל הא"ב {a,b,c}.

בשאלה האחרונה של אסנת, אסתי ואורנה דנו בתת-שפה שהיא דומה מאוד לשפה זו

(שפת כל המילים מעל הא"ב {a,b} מהצורה w×R(w)) ובנינו עבורה מכונת טיורינג.

יש לערוך במכונה את ההתאמות הבאות:

א"ב הקלט יהיה כמובן {a,b,c} במקום {a,b}.

יש להוסיף מצב המקביל ל-t1 ו-t2 ויתייחס לאות c,

יש להוסיף מצב המקביל ל-t3 ו-t4  ויתייחס לאות c.

בהתאם יש להרחיב את קבוצת המעברים כך שתתייחס גם לשני המצבים החדשים ולאות c.

לא נפרט את המכונה המתאימה.

 

חזרה

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

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