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

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

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

 

שאלה 1

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

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

המצב ההתחלתי של האוטומט הוא מתוך קבוצת המצבים הראשונה. המצבים המקבלים יכולים להיות שייכים לכל אחת משתי קבוצות המצבים.

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

דוגמה: נציג אוטומט עם שני קלטים המקבל את זוגות כל המילים מעל הא"ב {a, b} שמכילות מספר זהה של אותיות a (למשל הזוג (a, a) שייך לשפה וכמוהו גם הזוגות (babab, abba), (bba, a) ).

 

קבוצת המצבים הראשונה של האוטומט היא {q0} וקבוצת המצבים השניה היא {q1}. q0 הוא המצב ההתחלתי וגם המצב המקבל היחיד:

 

 

נשים לב כי במצב q0 האוטומט קורא אותיות במילה הראשונה ואילו במצב q1 הוא קורא אותיות מהמילה השנייה. כאשר הוא קורא a במילה הראשונה הוא עובר לחפש אות a במילה השנייה ואז חוזר לקריאת המילה הראשונה באותו מקום בו הפסיק אותה.

 

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

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

 

פתרון

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

א. קבוצת המצבים הראשונה: {q0}. קבוצת המצבים השנייה: {q1, q2}. המצב ההתחלתי הוא q0 והוא גם המצב המקבל היחיד.

 

 

ב. קבוצת המצבים הראשונה: {q0, q1}. קבוצת המצבים השניה {q2, q3}. q0 הוא המצב ההתחלתי והמצבים המקבלים הם q0 ו- q2.

 

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

 

 

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

 

שאלה 2

נגדיר אוטומט סופי דטרמיניסטי מהיר בדומה להגדרת אוטומט סופי דטרמיניסטי בספר לתלמיד, בהבדל אחד. במודל החדש פונקציית המעברים מתאימה לכל מצב q ושתי אותיות s1 ו- s2 מצב אחד ויחיד 'q.

המשמעות היא שכאשר האוטומט נמצא במצב q קריאת האות s1 ומיד אחריה קריאת האות s2 מביאה את האוטומט למצב 'q. כלומר, אוטומט מהמודל החדש קורא כל פעם זוג אותיות במקום אות אחת. אם מילת הקלט באורך אי זוגי, האוטומט "נתקע" לפני קריאת האות האחרונה, והמילה אינה מתקבלת.

הראה כי שפה המתקבלת על ידי אוטומט כזה היא שפה רגולרית שכל מילותיה באורך זוגי.

 

פתרון

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

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

קבוצת המצבים של האוטומט החדש תכיל את אותם מצבים כמו באוטומט המקורי A ובנוסף, לכל מעבר  (qi, σk, σ, qj) של האוטומט A יהיה מצב חדש qikℓj. המצב ההתחלתי, א"ב הקלט וקבוצת המעברים המקבלים של האוטומט החדש יהיו כמו אלו של A.

קבוצת המעברים תוגדר באופן הבא:

עבור  כל  מעבר  (qi, σk, σ, qj)  של  האוטומט A יהיו שני מעברים באוטומט החדש: (qi, σk, qikℓj) ו-(qikℓj, σ, qj).

כלומר, המעבר בו נקראות בבת אחת שתי אותיות בזו אחר זו יוחלף בסידרה של שני מעברים הקוראת את האותיות – כל אחת בתורה – תוך שימוש במצב ביניים.

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

 

חזרה

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

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