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

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

איריס ברגורי צור

 

שאלה 1

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

L={aibi+k-jcjdk½i,j,k>0, k>j}

פתרון

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

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

q0 – המצב ההתחלתי שבו נקראות אותיות a מהקלט ונדחפות אותיות A למחסנית.

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

q2 – מצב מילוי, אליו עובר האוטומט אחרי שהתרוקנה המחסנית בעקבות קריאת אותיות b ובו הוא נשאר כל עוד נקראות אותיות b.

q3 – מצב מילוי, אליו עובר האוטומט עם קריאת אותיות c.

q4 – מצב שליפה, אליו עובר האוטומט עם קריאת אותיות d.

q5 – מצב מקבל.

המעברים:

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

(q0,a,^,q0,A)

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

(q0,a,A,q0,AA)

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

(q0,b,A,q1,ε)

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

(q1,b,A,q1,ε)

קריאת b ראשונה אחרי התרוקנות המחסנית –

(q1,b,^,q2,S)

קריאת b שניה אחרי התרוקנות המחסנית –

(q2,b,S,q2,SA)

קריאת b שלישית ויותר אחרי התרוקנות המחסנית –

(q2,b,A,q2,AA)

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

(q2,c,A,q3,AA)

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

(q3,c,A,q3,AA)

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

(q3,d,A,q4,ε)

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

(q4,d,A,q4,ε)

קריאת d המובילה להתרוקנות המחסנית 

(q4,d,S,q5,ε)

א"ב המחסנית הוא כמובן {S,A}

 

חזרה

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

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