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

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

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

 

שאלה 1

לפניך מכונת טיורינג:

 

א. איזו שפה מתקבלת ע"י המכונה? נמק את תשובתך.

ב. האם שפה זו רגולרית? חופשית הקשר שאינה רגולרית? אינה חופשית הקשר? נמק את תשובתך.

 

פתרון

זאת שאלה קלה מאוד, שמתאימה לעבודת כיתה, שיעורי בית או בחינה.

א. המכונה מקבלת את שפת כל המילים שמכילות את הרצף ba או את הרצף ca.

ב. זו שפה רגולרית כי ניתן לבנות אוטומט סופי שמקבל אותה.

 

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

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

 

שאלה 2

לפניך מכונת טיורינג:

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

ב. מהי קבוצת המילים מעל הא"ב {a,b} שעבורן המכונה לא עוצרת?

ג. שנה את המכונה, כך שתקבל אותן מילים, אך תעצור על כל מילת קלט.

ד. האם השפה שמקבלת המכונה רגולרית, חופשית הקשר שאינה רגולרית, אינה חופשית הקשר? נמק את תשובתך.

 

פתרון

א. המכונה מקבלת את כל המילים מעל הא"ב {a,b} שמתחילות ב-b, מסתיימות ב-a ואינן מכילות את הרצף bb.

ב. המכונה לא עוצרת עבור כל המילים שמתחילות ב-a או מכילות את הרצף bb.

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

   

ד. השפה היא רגולרית ואוטומט סופי שמקבל אותה דומה מאוד למכונה שבסעיף ג':

 

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

 

חזרה

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

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