הבדלים בין גרסאות בדף "אוטומט מחסנית"

נוספו 31 בתים ,  לפני 5 חודשים
מ
הסרת קישורים עודפים, הגהה
מ (←‏ביצוע חישוב: הגהה, עיצוב)
מ (הסרת קישורים עודפים, הגהה)
[[קובץ:Automateapile.png|ממוזער|250px|ייצוג גרפי של אוטומט מחסנית, באמצעות [[גרף מכוון]]. האוטומט מורכב מ-4 [[מצב (מדעי המחשב)|מצבים]]: 2שני מצבים מקבלים (מסומנים בעיגול כפול) ו-2ושני מצבים שאינם מקבלים (מסומנים בעיגול בודד).]]
ב[[מדעי המחשב]], '''אוטומט מחסנית''' (באנגליתב[[אנגלית]]: '''Pushdown automaton''', ובר"תוב[[ראשי תיבות]]: '''PDA''') הוא [[מודל חישובי]], שמהווה הרחבה של [[מודל מתמטי|מודל]] ה[[אוטומט סופי|אוטומט הסופי]] (ה[[אוטומט סופי דטרמיניסטי|דטרמיניסטי]]), על ידי הוספת [[מחסנית (מבנה נתונים)|מחסנית]], שבה האוטומט מסוגל לאחסן [[נתונים|מידע]] (משמע, לאוטומט יש יכולת זיכרון). ההרחבה מגדילה את [[חישוביות|כוחו החישובי]] של האוטומט; כלומר, את [[קבוצה (מתמטיקה)|קבוצת]] ה[[שפה פורמלית|שפות]] שהוא מסוגל לזהות. בגרסתו הסטנדרטית, מודל אוטומט המחסנית מסוגל לזהות בדיוק את כל [[שפה חסרת הקשר|השפות חסרות ההקשר]].
 
==תיאור לא פורמלי==
 
כאשר:
 
*<math>\ Q</math> היא קבוצת מצבי האוטומט. כל מצב בקבוצה זו הוא, בהכרח, אחד מהשניים: "מצב מקבל" או "מצב לא מקבל".
*<math>\ \Sigma</math> היא (קבוצת) א"ב הקלט. כל [[איבר (מתמטיקה)|איבר]] בקבוצה זו מכונה "אות".
*<math>(q,\sigma Z)\in\delta (q,\sigma,Z)</math> - האוטומט קורא את האות <math>\ \sigma</math> מהקלט ודוחף אותה למחסנית, מעל ראש המחסנית הקיים (ניתן לחשוב על כך כאילו האוטומט הוציא את האות <math>Z</math> מראש המחסנית ומיד דחף אותה חזרה, ואחריה דחף גם את האות <math>\ \sigma</math>).
*<math>(q,\varepsilon) \in \delta(q,\sigma,Z)</math> - האוטומט קורא את האות <math>\ \sigma</math> מהקלט ומוציא את האות <math>Z</math> מראש המחסנית, מבלי לדחוף למחסנית שום דבר אחר במקומה. בכך, נחשפת האות שמתחתיה (זו שהוכנסה ממש לפני האות <math>Z</math> למחסנית) ומהווה את ראש המחסנית החדש.
 
===תיאור חישוב===
על מנת לתאר חישובים באמצעות אוטומט מחסנית, נהוג להשתמש ב'''תיאור רגעי'''. תיאור רגעי הוא שלשה סדורה, שמכילה את כל המידע הנחוץ לחישוב הצעד הנוכחי (והצעדים הנותרים) של האוטומט: