PDA

צפה בגרסה המלאה : שאלה || אוטומט מחסנית



blablabla1
01-02-2014, 11:29
איך בונים אוטומט מחסנית שמקבל את כל המילים שמספר ה- a בהן כפול ממספר ה-b?
א"ב {a,b}

odp
02-02-2014, 16:49
זו מין מערכת כזו של זכויות וחובות, כך ש-a שווה לכמות זכות אחת, ו-b שווה לכמות של 2 חובות. מקבלים את המילה אם ורק אם כמות הזכויות שווה לכמות החובות.

תחשבי על זה שאת יכולה לדחוף למחסנית a בכל קבלת a, וכן למחוק 2 a מראש המחסנית בקבלת b. מקבלים את המילה אם ורק אם המחסנית ריקה.
כמה הערות למימוש:
1) זה לא בעיה לעבור למצב מקבל אם רואים שהמחסנית ריקה, אז כל הקטע של המצבים הוא די פשוט, והמצב המקבל היחיד הוא q0 (המצב ההתחלתי).
2) בשביל להוריד 2 a מראש המחסנית, משתמשים במצבים: אם נניח שאנחנו ב-q1 (תכף נדבר על המקרה שאנחנו ב-q0), אז מורידים a אחד ועוברים ל-q2. המצב q2 אומר שאנחנו צריכים תכף ומיד (מעבר אפסילון) להוריד עוד a אחד, ואז עוברים ל-q1 בחזרה.
3) מה קורה אם המחסנית ריקה ? (כלומר, אנחנו ב-q0) לשם כך, אנחנו צריכים להתחיל לספור את המינוסים. אם ראינו b במילה והמחסנית ריקה, אז נכניס פעמיים את -a למחסנית. אם יש a אחד במחסנית וראינו b, אז נעיף את ה-a ונשים מינוס a.
4) אם יש בראש המחסנית מינוס a וראינו a במילה, אז נעיף את המינוס a מהמחסנית.

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

הכי טוב שתעשי את טבלת המעברים ותבדקי אם עניתי על כל המקרים האפשריים.
בהצלחה ! :)