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

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

לאה יעקובוביץ

 

שאלה 1

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

{זוגי L={anbn+m+kcmdk½n,m,k ³ 0,n+m+ k

פתרון

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

א"ב המחסנית יהיה {S,A}. א"ב הקלט {a,b,c,d}.

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

q0 – מצב התחלתי ומצב מקבל (לקבלת המילה הריקה).

q1 – קריאת אותיות a.

q2 – קריאת אותיות b במספר זוגי וקטן ממספר האותיות a.

q3 – קריאת אותיות b במספר אי זוגי וקטן ממספר האותיות a או שווה לו.

q4 – קריאת אותיות b במספר זוגי ושווה למספר האותיות a. זהו מצב מקבל (לקבלת מילה בה m=k=0,n>0)

q5 – קריאת אותיות b במספר זוגי וגדול ממספר האותיות a.

q6 – קריאת אותיות b במספר אי זוגי וגדול ממספר האותיות a.

q7 – קריאת אותיות c.

q8 – קריאת אותיות d.

q9 – מצב מקבל, המזהה מילה מהצורה anbn+m+kcmdk כאשר m או k גדולים מ-0.

המעברים:

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

(q0,a,^,q1,S)

קריאת a שניה –

(q1,a,S,q1,SA)

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

(q1,a,A,q1,AA)

קריאת b ראשונה, כשלא נקראו לפניה אותיות a  

(q0,b,^,q6,S)

קריאת b ראשונה ,כאשר לפניה נקראה אות a אחת –

(q1,b,S,q3,ε)

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

(q1,b,A,q3,ε)

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

(q3,b,A,q2,ε)

קריאת b זוגית, שניה ויותר, המביאה לריקון המחסנית –

(q3,b,S,q4,ε)

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

(q3,b,^,q5,S)

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

(q2,b,A,q3,ε)

קריאת b אי זוגית, שלישית ויותר, המביאה לריקון המחסנית –

(q2,b,S,q3,ε)

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

(q4,b,^,q6,S)

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

(q5,b,S,q6,SA)

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

(q6,b,S,q5,SA)

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

(q5,b,A,q6,AA)

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

(q6,b,A,q5,AA)

קריאת c ראשונה אחרי שנקרא מספר זוגי של אותיות b, והיא אינה מביאה להתרוקנות המחסנית – 

(q5,c,A,q7,ε)

קריאת c ראשונה אחרי שנקרא מספר זוגי של אותיות b, והיא מביאה להתרוקנות המחסנית – 

(q5,c,S,q9,ε)

קריאת c שניה ויותר אחרי שנקרא מספר זוגי של אותיות b, והיא אינה מביאה להתרוקנות המחסנית – 

(q7,c,A,q7,ε)

קריאת c שניה ויותר אחרי שנקרא מספר זוגי של אותיות b, והיא מביאה להתרוקנות המחסנית – 

(q7,c,S,q9,ε)

קריאת d ראשונה אחרי שנקרא מספר זוגי של אותיות b, ולא נקראו אותיות c, והיא אינה מביאה להתרוקנות המחסנית – 

(q5,d,A,q8,ε)

קריאת d ראשונה אחרי שנקרא מספר זוגי של אותיות b, ולא נקראו אותיות c, והיא מביאה להתרוקנות המחסנית – 

(q5,d,S,q9,ε)

קריאת d ראשונה אחרי שנקראו אותיות c, ולפניהן נקרא מספר זוגי של אותיות b, והיא אינה מביאה להתרוקנות המחסנית   

(q7,d,A,q8,ε)

קריאת d ראשונה אחרי שנקראו אותיות c ולפניהן נקרא מספר זוגי של אותיות b, והיא מביאה להתרוקנות המחסנית – 

(q7,d,S,q9,ε)

קריאת d שניה ויותר אחרי שנקרא מספר זוגי של אותיות b, והיא אינה מביאה להתרוקנות המחסנית – 

(q8,d,A,q8,ε)

קריאת d שניה ויותר אחרי שנקרא מספר זוגי של אותיות b, והיא מביאה להתרוקנות המחסנית – 

(q8,d,S,q9,ε)

 

כדאי לשים לב לקווי הדמיון בין אוטומט זה לאוטומט שנבנה עבור שאלה 1 של איריס ברגורי, ולהבדלים ביניהם.

 

שאלה 2

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

{n זוגי,  m אי-זוגי L={a2nbmcn½ n,m ³ 0,

פתרון

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

א"ב המחסנית הוא {S,T}. א"ב הקלט {a,b}. לאוטומט תשעה מצבים:

q0 – מצב התחלתי, נקראו אותיות a במספר זוגי.

q1 – נקראו אותיות a במספר אי זוגי.

q2 – נקראו אותיות b במספר אי זוגי ולפניהן נקראו אותיות a.

q3 – נקראו אותיות b במספר זוגי ולפניהן נקראו אותיות a.

q4 – נקראו אותיות b במספר אי זוגי ולפניהן לא נקראו אותיות a.

q5 – נקראו אותיות b במספר זוגי ולפניהן לא נקראו אותיות a.

q6 – נקראו אותיות c  במספר אי זוגי וקטן ממחצית מספר האותיות a שלפניהן.

q7 – נקראו אותיות c במספר זוגי וקטן ממחצית מספר האותיות a שלפניהן.

q8 – נקראו אותיות c במספר זוגי ושווה למחצית מספר האותיות a שלפניהן.

מצבים מקבלים: q4 ו- q8.

המעברים:

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

(q0,a,^,q1,ε)

קריאת a שניה –

(q1,a,^,q0,S)

קריאת a שלישית –

(q0,a,S,q1,ε)

קריאת a רביעית –

(q1,a,S,q0,SA)

קריאת a אי זוגית, חמישית ויותר –

(q0,a,A,q1,AA)

קריאת a זוגית, שישית ויותר –

(q1,a,A,q0,AA)

קריאת b ראשונה, כשלפניה לא נקראו אותיות a  

(q0,b,^,q4,ε)

קריאת b ראשונה, כשלפניה נקראו שתי אותיות a 

(q0,b,S,q2,S)

קריאת b ראשונה, כשלפניה מספר זוגי וגדול מ-2 של אותיות a

(q0,b,A,q2,A)

קריאת b זוגית, שניה ויותר, כשלפניה לא נקראו אותיות a

(q4,b,^,q5,ε)

קריאת b אי זוגית, שלישית ויותר, כשלפניה לא נקראו אותיות a

(q5,b,^,q4,ε)

קריאת b זוגית, שניה ויותר, כשלפניה נקראו שתי אותיות a

(q2,b,S,q3,S)

קריאת b  זוגית, שניה ויותר, כשלפניה מספר זוגי וגדול מ-2 של אותיות a

(q2,b,A,q3,A)

קריאת b אי זוגית, שלישית ויותר, כשלפניה נקראו שתי אותיות a

(q3,b,S,q2,S)

קריאת b אי זוגית, שלישית ויותר, כשלפניה מספר זוגי וגדול מ-2 של אותיות a

(q3,b,A,q2,A)

קריאת c ראשונה, כשלפניה מספר זוגי וגדול מ-2 של אותיות a, ומספר אי זוגי של אותיות b

(q2,c,A,q6,ε)

קריאת c זוגית, שניה ויותר, כשלפניה מספר אי זוגי של אותיות b, והיא אינה מביאה להתרוקנות המחסנית 

(q6,c,A,q7,ε)

קריאת c זוגית, שניה ויותר, כשלפניה מספר אי זוגי של אותיות b, והיא מביאה להתרוקנות המחסנית 

(q6,c,S,q8,ε)

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

(q7,c,A,q6,ε)

 

 שימו לב כי אין מעברים המתאימים לאות c במצבים q2 ן- q7 כאשר בראש המחסנית נמצאת S. בכך אין אנו מאפשרים לקבל מילים בהן מספר האותיות c אי זוגי.

 

חזרה

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

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