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

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

ריקה רם

 

שאלה 1

בנה אוטומט מחסנית עבור השפה הבאה מעל הא"ב {a,b,c}:

L={an(cw)kcbn+1½n,k >0, wÎ{ambm½m >0}}

 

פתרון

האוטומט יעבוד עפ"י האלגוריתם הבא:

עם קריאת האות a הראשונה ידחוף למחסנית אות לסימון תחתית ועוד אות A. אח"כ ידחוף למחסנית אות A על כל אות a שנקראת.

בהגיע אות c יעבור למצב חדש ואז עם קריאת אותיות a ידחוף שוב אותיות A למחסנית תוך סימון תחתית חדשה וירוקן את האותיות עם קריאת אותיות b וחוזר חלילה עד שאחרי האות c מופיעה האות b. במקרה זה ירוקן את המחסנית עם קריאת אותיות b עד להתרוקנותה המלאה.

לאוטומט שמונה מצבים:

q0 – מצב התחלתי בו נקרא רצף האותיות a הראשון.

q1 – מצב אחרי קריאת c ראשון.

q2 – קריאת רצף a פנימי.

q3 – קריאת רצף b פנימי.

q4 – מצב שוויון של רצף a פנימי ורצף b פנימי.

q5 – מצב אחרי קריאת c שני ויותר.

q6 – קריאת רצף b חיצוני.

q7 – שוויון באורך הרצפים החיצוניים.

א"ב המחסנית הוא {S,A,T} המצב המקבל הוא q7.

קבוצת המעברים:

קריאת a ראשונה ברצף הפותח –

(q0,a,^,q0,SA)

קריאת a שניה ויותר ברצף הפותח –

(q0,a,A,q0,AA)

נקראה c

(q0,c,A,q1,A)

קריאת a ראשונה ברצף פנימי – 

(q1,a,A,q2,T)

קריאת a שניה ברצף פנימי –

(q2,a,T,q2,TA)

קריאת a שלישית ויותר ברצף פנימי –

(q2,a,A,q2,AA)

קריאת b ראשונה ברצף פנימי, כשהתחתית השניה אינה גלויה –

(q2,b,A,q3,ε)

קריאת b ראשונה ברצף פנימי, כשהתחתית השניה גלויה –

(q2,b,T,q4,ε)

קריאת b שניה ויותר ברצף פנימי, כשהתחתית השניה אינה גלויה –

(q3,b,A,q3,ε)

קריאת b שניה ויותר ברצף פנימי, כשהתחתית השניה גלויה –

(q3,b,T,q4,ε)

נקראה c אחרי רצף פנימי אחד –

(q4,c,A,q5,ε)

נקראה a המתחילה רצף פנימי נוסף 

(q5,a,A,q2,T)

נקראה b המתחילה רצף חיצוני –

(q5,b,A,q6,ε)

נקראה b שניה ויותר ברצף חיצוני 

(q6,b,A,q6, ε)

נקראה b ברצף חיצוני המביאה לריקון המחסנית –

(q6,b,S,q7,ε)

 

חזרה

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

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