אוטומט מחסנית – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
←תיאור לא פורמלי: ניסוח |
שמירת ביניים (כלל הערך, עד פסקת "תיאור חישוב"): קישורים פנימיים, תיקון, עריכה והגהה, ועוד (שיפור הקריאות, והורדת סף הידע המקדים הנדרש לקריאה). |
||
שורה 1:
[[תמונה:Automateapile.png|ממוזער|250px|ייצוג גרפי של אוטומט מחסנית, באמצעות [[גרף מכוון]]. האוטומט מורכב מ-4 [[מצב (מדעי המחשב)|מצבים]]: 2 מצבים מקבלים (מסומנים בעיגול כפול) ו-2 מצבים שאינם מקבלים (מסומנים בעיגול בודד).]]
ב[[מדעי המחשב]], '''אוטומט מחסנית''' הוא [[מודל חישובי]], שמהווה הרחבה של [[מודל מתמטי|מודל]] ה[[אוטומט סופי
==תיאור לא פורמלי==
בדומה לאוטומט הסופי הדטרמיניסטי, אוטומט המחסנית מורכב מאוסף של '''[[מצב (מדעי המחשב)|מצבים]]''', המקבילים למצבי הזיכרון בהם
ההבדל המרכזי שבין [[אוטומט סופי]] ובין אוטומט מחסנית הוא התקן הזיכרון הנוסף, שעומד לרשות אוטומט המחסנית
=== ביצוע חישוב ===
בכל צעד [[חישוב (מדעי המחשב)|חישוב]] שלו, אוטומט המחסנית מחליט על דרך הפעולה שלו, בהתבסס על שלושה נתונים:
* האות שהוא קורא מהקלט (אם כי הוא אינו מחויב לקרוא אות מהקלט בכל צעד).
המודל הסטנדרטי של אוטומט המחסנית הוא [[אי דטרמיניזם|אי דטרמיניסטי]] - בכל צעד חישוב האוטומט מסוגל לבצע מספר בחירות שונות, ולכן ניתן לתאר חישובים שונים רבים שהוא מבצע על כל מילת קלט, ודי בכך שבחישוב אחד האוטומט יכריע כי מילת הקלט שייכת לשפה אותה הוא מזהה. ניתן להגדיר גם מודל דטרמיניסטי של אוטומט מחסנית, אך מתברר כי מודל זה הוא בעל יכולת חישובית פחותה ממש מזו של המודל האי דטרמיניסטי - קיימות שפות אותן המודל האי דטרמיניסטי מסוגל לזהות והמודל הדטרמיניסטי לא. בכך נבדל אוטומט המחסנית הן מהאוטומט הסופי והן ממודל החישוב הכללי יותר, של [[מכונת טיורינג]] - בשני המודלים הללו מתקיימת שקילות מבחינת כוח החישוב בין המודל הדטרמיניסטי ובין המודל האי דטרמיניסטי.▼
* האות שנמצאת בראש המחסנית.
* המצב הפנימי שלו (שם המצב + מצב המחסנית).
לאחר שהחליט, הוא עובר למצב פנימי חדש (לא בהכרח אחר), תוך כדי שינוי תוכן המחסנית, באחד משלושה אופנים:
* הוצאת אות אחת בלבד מראש המחסנית (ב[[אנגלית]], פעולת Pop).
* אי-ביצוע כל שינוי במחסנית (לא הכנסה ולא הוצאה של אותיות; משמע, רק "הצצנו"/הסתכלנו על האות שבראש המחסנית).
* דחיפת (הכנסת) לתוכה במקומה אותיות אחרות (באנגלית, פעולת Push).
▲המודל הסטנדרטי של אוטומט המחסנית הוא [[אי
==תיאור פורמלי==
{{סימון מתמטי}}[[מודל מתמטי|תיאור מתמטי פורמלי]] של אוטומט מחסנית <math>\ A</math> הוא באמצעות
<math>\ A=\left\{Q,\Sigma,\Gamma,\delta,q_0,\dashv,F\right\}</math>
שורה 18 ⟵ 25:
כאשר:
*<math>\ Q</math> היא קבוצת מצבי האוטומט. כל מצב בקבוצה זו הוא, בהכרח, אחד מהשניים: "מצב מקבל" או "מצב לא מקבל".
*<math>\ \Sigma</math>
*<math>\ \Gamma</math>
* <math>\ \delta :Q\times\left(\Sigma\cup\left\{\varepsilon\right\}\right)\times\Gamma\to \mathrm{P}\left(Q\times\Gamma^*\right)</math> היא [[פונקציית מעברים|פונקציית המעברים]] (הערה: ).
*<math>\ q_0</math> הוא המצב ההתחלתי (ממנו מתחיל החישוב) <math>\ q_0\isin Q</math>.
*<math>\ \dashv</math> היא האות ההתחלתית שבמחסנית - תמיד! זוהי אות שמורה מיוחדת, שמשמעותה בפועל היא שהמחסנית ריקה, כי למחסנית ריקה באמת יש משמעות מעשית אחרת באוטומט מחסנית.
*<math>\ F</math> היא קבוצת המצבים המקבלים, <math>\ F\subseteq Q</math>. מצב מקבל הוא מצב שמסמן שהאוטומט מחזיר תשובה חיובית. כלומר: אם בסוף הקלט האוטומט נמצא במצב מקבל, זה אומר שהקלט הוא מילה בשפה שהאוטומט מזהה.
משמעותה של פונקציית המעברים היא זו
* המצב הנוכחי של האוטומט (שם המצב), * האות שמופיעה בראש המחסנית, * האות הבאה שהוא קורא מהקלט (או [[מחרוזת ריקה (תכנות)|המילה הריקה]] <math>\ \varepsilon</math>, אם רוצים לתאר מעבר, שאינו כולל קריאת מילה מהקלט) פעולת האוטומט תהיה לעבור למצב אחר (או להישאר במצב שבו מכיוון שהאוטומט אי
פונקציית המעברים [[תחום הגדרה|אינה מוגדרת]], כאשר המחסנית ריקה
להלן מספר דוגמאות לפעולת פונקציית המעברים, שבכולן האוטומט מתחיל במצב <math>\ q</math> ונשאר בו:
*<math>\ (q,Z)\in\delta (q,\sigma,Z)</math> - האוטומט קורא את <math>\ \sigma</math> מהקלט ואינו משנה את ראש המחסנית (ניתן לחשוב על כך כאילו הוא הוציא את האות <math>\ Z</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>\ \left(q,w,\gamma\right)</math> כך ש-<math>\ q\in Q</math> הוא המצב הנוכחי, <math>\ w\in\Sigma^*</math> היא מילת הקלט שטרם נקראה, ו-<math>\ \gamma\in\Gamma^*</math> הוא תוכנה הנוכחי של המחסנית.
| |||