אוטומט מחסנית – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ בוט החלפות: דוגמה; זיכרון; |
מ קישור |
||
שורה 7:
ההבדל המרכזי שבין אוטומט סופי ובין אוטומט מחסנית הוא התקן הזיכרון הנוסף שעומד לרשות אוטומט המחסנית - מחסנית שמאפשרת אחסון נתונים. המחסנית מאכסנת אותיות (מעל אלפבית סופי וידוע מראש, אך לא בהכרח האלפבית שממנו בנויה מילת הקלט) בצורה סדרתית, כך שהאות האחרונה שהוכנסה למחסנית נמצאת בראשה, אחריה האות שהוכנסה לפניה למחסנית, וכן הלאה (שיטת [[LIFO]]). בצורה זו הגישה לזיכרון מוגבלת מאוד - ניתן לראות בכל פעם רק את האות שבראש המחסנית, וכדי לראות אות שבתוך המחסנית יש להוציא מהמחסנית את כל האותיות שמעליה (ובכך "לאבד" אותן, שכן אין מקום אחסון נוסף עבורן).
בכל צעד [[חישוב (מדעי המחשב)|חישוב]] שלו, אוטומט המחסנית מחליט על דרך הפעולה שלו בהתבסס של שלושה נתונים - האות שהוא קורא מהקלט (אם כי הוא אינו מחויב לקרוא אות מהקלט בכל צעד), האות שנמצאת בראש המחסנית, והמצב הפנימי שלו. לאחר שהחליט, הוא עובר למצב פנימי אחר, ומשנה את תוכן המחסנית באופן מסוים - הוא יכול להוציא מהמחסנית את האות שבראשה, ולדחוף לתוכה במקומה אותיות אחרות.
המודל הסטנדרטי של אוטומט המחסנית הוא [[אי דטרמיניזם|אי דטרמיניסטי]] - בכל צעד חישוב האוטומט מסוגל לבצע מספר בחירות שונות, ולכן ניתן לתאר חישובים שונים רבים שהוא מבצע על כל מילת קלט, ודי בכך שבחישוב אחד האוטומט יכריע כי מילת הקלט שייכת לשפה אותה הוא מזהה. ניתן להגדיר גם מודל דטרמיניסטי של אוטומט מחסנית, אך מתברר כי מודל זה הוא בעל יכולת חישובית פחותה ממש מזו של המודל האי דטרמיניסטי - קיימות שפות אותן המודל האי דטרמיניסטי מסוגל לזהות והמודל הדטרמיניסטי לא. בכך נבדל אוטומט המחסנית הן מהאוטומט הסופי והן ממודל החישוב הכללי יותר, של [[מכונת טיורינג]] - בשני המודלים הללו מתקיימת שקילות מבחינת כוח החישוב בין המודל הדטרמיניסטי ובין המודל האי דטרמיניסטי.
| |||