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

מודלים אלטרנטיביים

רחלי צרניחוב

 

שאלה 1

נגדיר מודל חדש: אוטומט דו-תור. זהו אוטומט לא דטרמיניסטי המצוייד בדו-תור, כלומר, בשני תורות, ובכל צעד הוא יכול לשלוף אות מראש כל אחד מהתורות ולדחוף מילה בסוף כל אחד מהתורות.

האם אוטומט דו-תור הוא חזק יותר מאוטומט מחסנית, חלש יותר מאוטומט מחסנית או שווה לו בכוחו? נמק.

 

פתרון

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

מודל אוטומט דו-תור הוא חזק יותר מאוטומט מחסנית. לשם כך יש להראות כי כל שפה חופשית הקשר ניתנת לקבלה ע"י אוטומט דו-תור וכי קיימת שפה שאינה חופשית הקשר שניתנת לקבלה ע"י אוטומט דו-תור.

לכיוון השני תתאים למשל השפה {w מעל הא"ב {w×w ï{a, b}.

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

בכיוון הראשון נראה כי כל פעולה באוטומט מחסנית ניתנת לביצוע ע"י סדרת פעולות באוטומט דו-תור.

אם במחסנית נמצאת סדרת האותיות

X

Y

Z

...

W

 

ואוטומט המחסנית צריך לשלוף את האות X ולדחוף את המילה G1, ..., Gn כלומר, להגיע למחסנית

 

Gn

...

G1

Y

Z

...

W

 

נראה כי אוטומט דו-תור יכול לבצע סדרת פעולות בה הוא מתחיל מתור אחד ריק ומתור אחד המכיל

 

ראש

X

 

Y

 

Z

 

...

סוף

W

 

ובסיומה יש בידו תור אחד ריק ותור אחד המכיל

ראש

Gn

 

...

 

G1

 

Y

 

Z

 

....

סוף

W

 

 

שאלה 2

תלמיד טען את הטענה הבאה: אם נוכל להוסיף מחסנית נוספת לאוטומט מחסנית נוכל לקבל כל שפה שנרצה.

האם הטענה נכונה? נמק את תשובתך!

 

פתרון

הטענה לא נכונה.

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

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

 

חזרה

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

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