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

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

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

 

שאלה 1

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

L={anbmck½n,m,k>0,k ³ n+m}

פתרון

שאלה זו מתאימה לעבודת כיתה או לשיעורי בית, אחרי שהתלמידים דנו בשאלה 5.13 בספר לתלמיד.

לאוטומט ארבעה מצבים, q3 מצב מקבל:

q0 – מצב התחלתי. זוכר שעד כה נקראו רק אותיות a.

q1 – זוכר שעד כה נקרא רצף לא ריק של אותיות a ואחריו רצף לא ריק של אותיות b.

q2 – זוכר שעד כה נקרא רצף לא ריק של אותיות  a ואחריו רצף לא ריק של אותיות b ואחריו רצף לא ריק של אותיות c, כאשר מספר האותיות c שנקראו עד כה קטן מסכום מספר האותיות a ומספר האותיות  b שנקראו.

q3 – זוכר שעד כה נקרא רצף לא ריק של אותיות a, ואחריו רצף לא ריק של אותיות b ואחריו רצף לא ריק של אותיות c, כאשר מספר האותיות c שנקראו עד כה אינו קטן מסכום מספר האותיות a ומספר האותיות b שנקראו.

א"ב המחסנית של האוטומט הוא {S,A}.

המעברים:

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

(q0,a,^,q0,S)

קריאת a שניה –

(q0,a,S,q0,SA)

קריאת a שלישית ויותר -

(q0,a,A,q0,AA)

קריאת b ראשונה כאשר נקראה קודם אות a אחת – 

(q0,b,S,q1,SA)

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

(q0,b,A,q1,AA)

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

(q1,b,A,q1,AA)

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

(q1,c,A,q2,ε)

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

(q2,c,A,q2,ε)

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

(q2,c,S,q3,ε)

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

(q3,c,^,q3,ε)

 

 

חזרה

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

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