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

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

אסנת אנגלמן, אסתי מאסטרסי, ארנה אברך-שטיין

 

שאלה 1

בנה אוטומט מחסנית המקבל את כל המילים מעל הא"ב {0,1} בהן מספר האותיות 0 שווה למספר האותיות 1 והן מייצגות מספר בינארי זוגי.

פתרון

האוטומט דומה מאוד לאוטומט שנתון במדריך למורה כפתרון לתרגיל 5.19 מהספר לתלמיד. כמובן, יש להחליף כל a ב- 0 וכל b ב- 1. בשפה הנדונה המילה הריקה אינה מספר בינארי ולכן בפרט אינה מספר בינארי זוגי, כלומר היא אינה בשפה. לכן יש להוסיף מצב התחלתי חדש q0 שאינו מצב מקבל. את שני המצבים הזוכרים שוויון ואי שוויון של מספר האותיות 0 (a באוטומט המקורי) ומספר האותיות 1 (b באוטומט המקורי) יש להכפיל באופן הבא:

q1 – מצב הזוכר שוויון במספר האותיות 0 ומספר האותיות 1 שנקראו עד כה, וזוכר כי האות האחרונה שנקראה היא 0.

q2 – מצב הזוכר אי-שוויון במספר האותיות 0 ומספר האותיות 1 שנקראו עד כה, וזוכר כי האות האחרונה שנקראה היא 0.

q3 – מצב הזוכר שוויון במספר האותיות 0 ומספר האותיות 1 שנקראו עד כה, וזוכר כי האות האחרונה שנקראה היא 1.

q4 – מצב הזוכר אי-שוויון במספר האותיות 0 ומספר האותיות 1 שנקראו עד כה, וזוכר כי האות האחרונה שנקראה היא 1.

א"ב הקלט הוא {0,1}. א"ב המחסנית {S,T,A,B} , q1 הוא המצב המקבל.

המעברים:

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

(q0,0,^,q2,S)

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

(q0,1,^,q4,T)

קריאת אות 0 כאשר יש עודף אות 0 אחת, והאות האחרונה שנקראה היא 0 –

(q2,0,S,q2,SA)

קריאת אות 0 כאשר יש עודף אותיות 0, והאות האחרונה שנקראה היא 0 –

(q2,0,A,q2,AA)

קריאת אות 0 כאשר יש עודף של אות 1 אחת, והאות האחרונה שנקראה היא 0 –

(q2,0,T,q1,ε)

קריאת אות 0 כאשר יש עודף אותיות 1, והאות האחרונה שנקראה היא 0 –

(q2,0,B,q2,ε)

קריאת אות 1 כאשר יש עודף של אות 0 אחת, והאות האחרונה שנקראה היא 0 –

(q2,1,S,q3,ε)

קריאת אות 1 כאשר יש עודף אותיות 0, והאות האחרונה שנקראה היא 0 –

(q2,1,A,q4,ε)

קריאת אות 1 כאשר יש עודף אות 1 אחת, והאות האחרונה שנקראה היא 0 –

(q2,1,T,q4,TB)

קריאת אות 1 כאשר יש עודף אותיות 1, והאות האחרונה שנקראה היא 0 –

(q2,1,B,q4,BB)

קריאת אות 0 כאשר יש שוויון במספר האותיות 0 ומספר האותיות 1 שנקראו עד כה, והאות האחרונה שנקראה היא 0 –

(q1,0,^,q2,S)

קריאת אות 1 כאשר יש שוויון במספר האותיות 0 ומספר האותיות 1 שנקראו עד כה, והאות האחרונה שנקראה היא 0 –

(q1,1,^,q4,T)

קריאת אות 0 כאשר יש שוויון במספר האותיות 0 ומספר האותיות 1 שנקראו עד כה, והאות האחרונה שנקראה היא 1 –

(q3,0,^,q2,S)

קריאת אות 1 כאשר יש שוויון במספר האותיות 0 ומספר האותיות 1 שנקראו עד כה, והאות האחרונה שנקראה היא 1 –

(q3,1,^,q4,T)

קריאת אות 0 כאשר יש עודף אות 0 אחת, והאות האחרונה שנקראה היא 1 – 

(q4,0,S,q2,SA)

קריאת אות 0 כאשר יש עודף אותיות ,0 והאות האחרונה שנקראה היא 1 – 

(q4,0,A,q2,AA)

קריאת אות 0 כאשר יש עודף של אות 1 אחת, והאות האחרונה שנקראה היא 1

(q4,0,T,q1,ε)

קריאת אות 0 כאשר יש עודף של אותיות 1, והאות האחרונה שנקראה היא 1 –

(q4,0,B,q2,ε)

קריאת אות 1 כאשר יש עודף של אות 0 אחת, והאות האחרונה שנקראה היא 1 –

(q4,1,S,q3,ε)

קריאת אות 1 כאשר יש עודף של אותיות 0, והאות האחרונה שנקראה היא 1 –

(q4,1,A,q4,ε)

קריאת אות 1 כאשר יש עודף של אות 1 אחת, והאות האחרונה שנקראה היא 1 –

(q4,1,T,q4,TB)

קריאת אות 1 כאשר יש עודף של אותיות 1, והאות האחרונה שנקראה היא 1 –

(q4,1,B,q4,BB)

 

 הערה: מאחר ובמקרה הכללי השפות חופשיות ההקשר אינן סגורות לחיתוך, לא יכולנו להסתמך על תכונת סגירות ולהסיק מכאן כי השפה הנדונה חופשית הקשר. אבל, שפה זו היא למעשה חיתוך של שפה חופשית הקשר (מספר האותיות 0 במילה שווה למספר האותיות 1 במילה) עם שפה רגולרית (המילה מייצגת מספר בינארי זוגי). חיתוך של שפה חופשית הקשר עם שפה רגולרית אכן נותן תמיד שפה חופשית הקשר (כלומר, השפות חופשיות ההקשר סגורות לפעולת החיתוך עם שפה רגולרית) אך זה משפט שאינו כלול בחומר הלימוד של היחידה ולכן לא ניתן להסתמך עליו. בהוכחת המשפט אכן נבנה אוטומט מכפלה (כמו ההוכחה עבור שפות רגולריות) ולמעשה, הבנייה הכללית המשמשת בהוכחת המשפט דומה מאוד לבנייה שבוצעה כאן.

 

שאלה 2

בבית חרושת מייצרים מחרוזות המורכבות מפנינים גדולות וקטנות, ובכל מחרוזת מספר הפנינים הקטנות שווה למספר הפנינים הגדולות. המחרוזת צריכה להתחיל ברצף של פנינים קטנות ולהסתיים ברצף של פנינים קטנות ובמרכזה רצף של פנינים גדולות. מחרוזת שאינה עומדת בתנאים אלו אינה עוברת את בדיקת האיכות.

א.      הגדר שפה שמתאימה לכל המחרוזות העומדות בבדיקת האיכות.

ב.       בנה אוטומט מחסנית הקובע אם מחרוזת נתונה עוברת את בדיקת האיכות.

פתרון

א.      השפה היא  {anbn+mam½n, m>0 } מעל הא"ב {a,b}.

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

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

q0 – מצב התחלתי, לקריאת אותיות a.
q1 – מצב לקריאת אותיות b עד התרוקנות המחסנית.
q2 – מצב לקריאת אותיות b ומילוי המחסנית.
q3 – מצב לקריאת אותיות a וריקון המחסנית.
q4 – מצב מקבל.
א"ב הקלט הוא
{a,b} וא"ב המחסנית {S,A}.
המעברים:


קריאת אות 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)

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

(q2,a,A,q3,ε)

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

(q2,a,S,q4,ε)

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

(q3,a,A,q3,ε)

קריאת אות a שניה ויותר ברצף השני, המביאה להתרוקנות המחסנית –

(q3,a,S,q4,ε)

 

חזרה

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

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