אוטומט מחסנית – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
הרחבה, תיקון פרמטרים, הפרת זכויות יוצרים תגיות: שוחזרה תיקון פרמטרים עריכה חזותית |
מ שוחזר מעריכות של 2A01:6500:A046:5871:F37D:8745:46C9:500 (שיחה) לעריכה האחרונה של Haparsi |
||
שורה 3:
==תיאור לא פורמלי==
בדומה לאוטומט הסופי הדטרמיניסטי, אוטומט המחסנית מורכב מאוסף של '''[[מצב (מדעי המחשב)|מצבים]]''', המקבילים למצבי הזיכרון בהם יכולה להימצא מכונת החישוב במהלך ביצוע חישוב. דרך הפעולה של האוטומט מבוססת על קריאת מילת [[קלט]] ([[מחרוזת (מדעי המחשב)|מחרוזת]], המורכבת מאלפבית סופי וידוע מראש) באופן סדרתי, אות אחת בכל פעם, עד אשר מסתיימת קריאת המילה, ואז מחזיר האוטומט תשובה – האם המילה שנקראה שייכת ל[[שפה פורמלית|שפה]] אותה מזהה האוטומט, או לא.
ההבדל המרכזי שבין [[אוטומט סופי]] ובין אוטומט מחסנית הוא התקן הזיכרון הנוסף, שעומד לרשות אוטומט המחסנית – מחסנית, שמאפשרת אחסון (שמירת) [[נתונים]]. המחסנית מאחסנת אותיות (מעל אלפבית סופי וידוע מראש, אך לא בהכרח האלפבית שממנו בנויה מילת הקלט) בצורה סדרתית, כך שהאות האחרונה שהוכנסה למחסנית נמצאת בראשה, אחריה האות שהוכנסה לפניה למחסנית, וכן הלאה, עד האות הראשונה שהוכנסה למחסנית, הנמצאת בתחתיתה (ונגישה להצצה או שליפה אחרונה מכולן) (שיטת [[LIFO]]). בצורה זו, הגישה לזיכרון מוגבלת מאוד – ניתן לראות בכל פעם רק את האות שבראש המחסנית, וכדי לראות אות שבתוך המחסנית, יש להוציא מהמחסנית את כל האותיות שמעליה (ובכך "לאבד" אותן, שכן אין מקום אחסון נוסף עבורן).
=== ביצוע חישוב ===
בכל צעד [[חישוב (מדעי המחשב)|חישוב]] שלו, אוטומט המחסנית מחליט על דרך הפעולה שלו, בהתבסס על שלושה נתונים:
* האות שהוא קורא מהקלט (אם כי הוא אינו מחויב לקרוא אות מהקלט בכל צעד),
| |||