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