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

בניית אוטומט מחסנית

אתי מנשה

 

שאלה 1

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

פתרון

ניתן לתאר את L באופן הבא:

n, m>n} זוגי {0n1mw½ n ³ 0,

מספר האותיות 1 ב- w + מספר האותיות 2 ב- w הוא ערך אי זוגי.

האוטומט יעבוד עפ"י האלגוריתם הבא: כל עוד נקראות אותיות 0 ידחוף אותיות למחסנית, תוך מעקב אחר זוגיות מספר האותיות 0. עם קריאת אותיות 1 יתחיל לרוקן את המחסנית. אחרי שהמחסנית התרוקנה, וכל עוד נקראות רק אותיות 1 הוא יחליט באופן אי-דטרמיניסטי אם הוא עדיין בחלק 1m או בחלק השלישי w. ברגע שנקראת אות 0 או אות 2 ברור שכבר עבר לחלק השלישי w.

בכל מקרה, בקוראו את החלק השלישי יעקוב אחר זוגיות מספר האותיות 0 והאותיות 1, ללא שימוש במחסנית.

א"ב הקלט הוא {0,1,2}. א"ב המחסנית הוא {A}. לאוטומט שישה מצבים:

q0 – מצב התחלתי המציין גם כי נקרא מספר זוגי של אותיות 0.

q1 – נקרא מספר אי זוגי של אותיות 0.

q2 – נקראו אותיות 1 במספר קטן או שווה למספר האותיות 0 שנקראו לפניהן, ומספר האותיות 0 שנקראו זוגי.

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

q4 – נקרא מספר זוגי של אותיות 0 ואח"כ מספר גדול מזה של אותיות 1 ובחלק השלישי נקרא מספר אי זוגי של אותיות 1 ואותיות 2. 

q5 – נקרא מספר זוגי של אותיות 0, ואח"כ מספר גדול מזה של אותיות 1, ובחלק השלישי נקרא מספר זוגי של אותיות 1 ואותיות 2.

המצב המקבל הוא q4.

המעברים:

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

(q0,0,^,q1,A)

קריאת אות 0 זוגית, שניה ויותר –

(q1,0,A,q0,AA)

קריאת אות 0 אי זוגית, שלישית ויותר –

(q0,0,A,q1,AA)

קריאת אות 1 ראשונה, כשלפניה לא נקראו אותיות 0 –

(q0,1,^,q3,ε)

קריאת אות 1 ראשונה, כשלפניה נקרא מספר זוגי וגדול מ-0 של אותיות 0 –

(q0,1,A,q2,ε)

קריאת אות 1, שניה ויותר, לפני התרוקנות המחסנית –

(q2,1,A,q2,ε)

קריאת אות 1, שניה ויותר, מייד אחרי התרוקנות המחסנית 

(q2,1,^,q3,ε)

קריאת אות 1 בחלק השני של המילה, אחרי התרוקנות המחסנית –

(q3,1,^,q3,ε)

ניחוש כי האות 1 הבאה פותחת את החלק השלישי של המילה 

(q3,1,^,q4,ε)

קריאת אות 0 הפותחת את החלק השלישי של המילה –

(q3,0,^,q5,ε)

קריאת אות 2 הפותחת את החלק השלישי של המילה –

(q3,2,^,q4,ε)

קריאת אות 0 בחלקה השלישי של המילה, כאשר מספר האותיות 2 ו-1 שנקראו אי זוגי –

(q4,0,^,q4,ε)

קריאת אות 1 בחלקה השלישי של המילה, כאשר מספר האותיות 1 ו-2 שנקראו אי זוגי –

(q4,1,^,q5,ε)

קריאת אות 2 בחלקה השלישי של המילה, כאשר מספר האותיות1 ו-2 שנקראו אי זוגי –

(q4,2,^,q5,ε)

קריאת אות 0 בחלקה השלישי של המילה, כאשר מספר האותיות 1 ו-2 שנקראו זוגי –

(q5,0,^,q5,ε)

קריאת אות 1 בחלקה השלישי של המילה, כאשר מספר האותיות 1 ו-2 שנקראו זוגי –

(q5,1,^,q4,ε)

קריאת אות 2 בחלקה השלישי של המילה, כאשר מספר האותיות1 ו-2 שנקראו זוגי –

(q5,2,^,q4,ε)

 

חזרה

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

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