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

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

דגנית מורן

 

שאלה 1

נגדיר מודל חישובי חדש: מכונת טיורינג חד-כיוונית.

מכונת טיורינג חד-כיוונית היא כמו מכונת טיורינג אך מותר לה לנוע רק ימינה.

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

א. ההגבלה אינה פוגעת בכוח החישוב של המודל.

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

ג. למכונת טיורינג חד-כיוונית כוח חישוב זהה לזה של אוטומט סופי.

 

פתרון

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

 

שאלה 2

נגדיר מודל חישובי חדש: אוטומט לא-דטרמיניסטי לחלוטין.

באוטומט ממודל זה יש את כל המעברים האפשריים. כלומר לכל זוג מצבים qi ו-qj ולכל אות קלט σ  קיים באוטומט המעבר ( qj,σ, qi).

אילו שפות ניתן לקבל בעזרת אוטומט ממודל זה? הצדק את קביעתך.

 

פתרון

נבחן שני מקרים אפשריים עבור אוטומט לא דטרמיניסטי לחלוטין מסויים A:

א. ל-A יש לפחות מצב מקבל אחד.

ב. ל-A אין אף מצב מקבל.

 

א.  אם ל-A יש לפחות מצב מקבל אחד אז ישנן שתי אפשרויות:

א1. המצב ההתחלתי אינו מצב מקבל. במקרה זה המילה הריקה אינה שייכת לשפה שמקבל A, אך כל מילה אחרת שייכת לשפה: עבור אות הקלט הראשונה במילה קיים מעבר מהמצב ההתחלתי לאיזשהו מצב מקבלqf  ועבור כל אות קלט נוספת יש מעבר לולאתי מ- qf לעצמו. לכן בסיום קריאת המילה האוטומט יימצא במצב מקבל.

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

 

ב.  כמובן שאם ל-A אין אף מצב מקבל, הוא מקבל את השפה הריקה.

 

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

 

חזרה

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

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