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

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

דורון זוהר

 

שאלה 1

בנה אוטומט מחסנית עבור השפה הבאה מעל הא"ב {x,y,z}:

L={ (yx)nzk(xy) j½n ³ 0, n<j, k ³ 0, k mod 2 = 0 }

פתרון

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

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

א"ב הקלט הוא {x,y,z}, א"ב המחסנית הוא {A}. לאוטומט שמונה מצבים:

q0 – מצב התחלתי בו נמצא האוטומט לפני קריאת רצף yx תורן.

q1 – אחרי קריאת y ברצף yx.

q2 – נקראו אותיות z במספר אי זוגי.

q3 – נקראו אותיות z במספר זוגי וגדול מ-0.

q4 – אחרי קריאת x ברצף xy.

q5 – אחרי קריאת y ברצף xy.

q6 – מצב מקבל. אחרי קריאת רצף xy, כאשר מספר הרצפים xy גדול ממש ממספר הרצפים yx.

q7 – אחרי קריאת x ברצף xy כאשר מספר הרצפים xy שנקראו קודם גדול ממש ממספר הרצפים yx.

המעברים:

קריאת y ברצף yx ראשון –

(q0,y,^,q1,ε)

קריאת x ברצף yx ראשון –

(q1,x,^,q0,A)

קריאת y ברצף yx שני ויותר –

(q0,y,A,q1,A)

קריאת x ברצף yx שני ויותר –

(q1,x,A ,q0,AA)

קריאת z ראשונה, כשלפניה לא נקרא אף רצף yx (n=0)

(q0,z,^,q2,ε)

קריאת z ראשונה, כשלפניה נקרא לפחות רצף yx אחד (n>0)

(q0,z,A,q2,A)

קריאת z זוגית, שניה ויותר, כשבתחילת המילה לא היו רצפי yx (n=0)  

(q2,z,^,q3,ε)

קריאת z זוגית, שניה ויותר, כשבתחילת המילה נקרא לפחות רצף yx  אחד (n>0)  

(q2,z,^,q3,A)

קריאת z אי זוגית, שלישית ויותר, כשבתחילת המילה לא היו רצפי yx (n=0)  

(q3,z,^,q2,ε)

קריאת z אי זוגית, שלישית ויותר, כשבתחילת המילה נקרא לפחות רצף yx אחד (n>0) –

(q3,z,A,q2,A)

קריאת x ברצף xy ראשון, כשלפני כן לא היו רצפי yx (n=0) ואותיות z (k=0)  

(q0,x,^,q4,ε)

קריאת x ברצף xy ראשון, כשלפני כן נקרא לפחות רצף yx  אחד, (n>0) ולא נקראו אותיות z (k=0)   

(q0,x,A,q4,A)

קריאת x ברצף xy ראשון, כשלפני כן לא היו רצפי yx (n=0), ונקרא מספר זוגי וגדול מ- 0 של אותיות z (k>0) – 

(q3,x,^,q4,ε)

קריאת x ברצף xy ראשון, כשלפני כן נקרא לפחות רצף yx אחד (n>0), ונקרא מספר זוגי וגדול מ-0 של אותיות z (k>0) – 

(q3,x,A,q4,A)

קריאת y ברצף xy, מיד אחרי התרוקנות המחסנית –

(q4,y,^,q6,ε)

קריאת y ברצף xy, לפני התרוקנות המחסנית –

(q4,y,A,q5,ε)

קריאת x ברצף xy שני ויותר, מיד אחרי התרוקנות המחסנית 

(q5,x,^,q4,ε)

קריאת x ברצף xy שני ויותר, לפני התרוקנות המחסנית 

(q5,x,A,q4,A)

קריאת y ברצף xy, אחרי שהמחסנית כבר התרוקנה –

(q6,y,^,q7,ε)

קריאת x ברצף xy, אחרי שהמחסנית כבר התרוקנה 

(q7,x,^,q6,ε)

 

חזרה

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

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