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

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

אסנת אנגלמן, אסתי מאסטראסי, אורנה אברך-שטיין

 

שאלה 1

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

מצבים, מצב התחלתי, מצבים מקבלים, א"ב מחסנית, א"ב תור, ומעברים.

לפני שנתאר את קבוצת המעברים נציין כי:

הסימון ^ מסמן מחסנית ריקה.

הסימון  ╧ מסמן תור ריק

והסימון  N מציין התעלמות מראש התור (כפי שיוסבר להלן).

מעבר של אוטומט מחסנית הוא מהצורה (qi, s, G, qj, w).

σ היא אות קלט, וייתכנו אחת מ- 2 האפשרויות הבאות:

1. Γ אות מא"ב המחסנית או סימן כי המחסנית ריקה (^) ו- w מילה מעל א"ב המחסנית.

2. Γ אות מא"ב התור או סימן כי התור ריק (╧) או הסימן המיוחד  N ו- w מילה מעל א"ב התור.

במקרה הראשון משמעות המעבר היא שליפת האות Γ מראש המחסנית (אם אינה ריקה) ודחיפת המילה w למחסנית, כמו באוטומט מחסנית. במקרה השני, אם Γ היא הסימן  N אז המשמעות היא לדחוף את המילה w לסוף התור, ואחרת המשמעות היא לשלוף את האות Γ מראש התור (אם אינו ריק) ולדחוף את המילה w לסוף התור.

המודל הוא לא דטרמיניסטי.

הראה כיצד ניתן לקבל בעזרת אוטומט מחסנית-תור את השפה הבאה מעל הא"ב {a, b}:

w=R(w1)} או L={w×w1| w=w1

פתרון

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

א"ב הקלט יהיה {a, b}, א"ב המחסנית יהיה {X, Y, S, T} וא"ב התור יהיה {Z, R, P, Q}. לאוטומט 6 מצבים:

q0 – מצב התחלתי ומצב מקבל.

q1 – האוטומט ניחש כי המילה מהצורה w×R(w) והוא קורא את חלקה הראשון.

q2 – האוטומט ניחש כי המילה מהצורה w×R(w) והוא קורא את חלקה השני.

q3 – האוטומט ניחש כי המילה מהצורה w×w והוא קורא את חלקה הראשון.

q4 – האוטומט ניחש כי המילה מהצורה w×w והוא קורא את חלקה השני.

q5 – סיום קריאת מילה מהצורה w×R(w) או מהצורה w×w. מצב מקבל.

לאוטומט המעברים הבאים:

האוטומט ניחש כי המילה מהצורה w×R(w) 

והאות הראשונה שנקראה היא a

האוטומט ניחש כי המילה מהצורה w×R(w) 

והאות הראשונה שנקראה היא b

קריאת אות שניה

בחלק הראשון של מילה מהצורה w×R(w) 

קריאת אות שלישית ויותר

בחלק הראשון של מילה מהצורה w×R(w)    

ניחוש נקודת האמצע

במילה מהצורה w×R(w) בת שתי אותיות  

ניחוש נקודת האמצע במילה מהצורה w×R(w)

שלה יותר משתי אותיות  

קריאת החלק השני של מילה מהצורה w×R(w)

סיום קריאת מילה מהצורה w×R(w)

האוטומט ניחש כי המילה מהצורה w×w 

והאות הראשונה שנקראה היא a

האוטומט ניחש כי המילה מהצורה w×w 

והאות הראשונה שנקראה היא b  

קריאת אות שנייה ויותר בחלק הראשון של מילה מהצורה w×w  

קריאת אות שנייה ויותר בחלק הראשון של מילה מהצורה w×w

וניחוש כי אות זו מסיימת את החלק הראשון –

קריאת אות ראשונה בחלק הראשון של מילה מהצורה w×w

וניחוש כי אות זו מסיימת את החלק הראשון –

קריאת החלק השני של מילה מהצורה w×w

סיום קריאת מילה מהצורה w×w

 

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

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

 

שאלה 2

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

 

פתרון

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

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

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

 

נוסיף מצב חדש qF והוא יהיה המצב המקבל היחיד.

עתה, לכל מעבר (qj , qi) כאשר qi מצב כלשהו, qj מצב מקבל ו-σ אות קלט,

נוסיף גם את המעבר .

 

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

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

 

חזרה

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

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