אוטומט מחסנית – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
שמירת ביניים (כלל הערך, עד פסקת "תיאור חישוב"): קישורים פנימיים, תיקון, עריכה והגהה, ועוד (שיפור הקריאות, והורדת סף הידע המקדים הנדרש לקריאה).
המשך של העריכה הקודמת עד סוף הערך (ותיקון פספוסים קטנים גם מהחלק הקודם). ניתן לשקול מיזוג זהיר של שני תת-פרקי אופן ביצוע החישוב.
שורה 9:
=== ביצוע חישוב ===
בכל צעד [[חישוב (מדעי המחשב)|חישוב]] שלו, אוטומט המחסנית מחליט על דרך הפעולה שלו, בהתבסס על שלושה נתונים:
* האות שהוא קורא מהקלט (אם כי הוא אינו מחויב לקרוא אות מהקלט בכל צעד).,
* המצב הפנימי שלו (שם המצב + מצב המחסנית).,
* האות שנמצאת בראש המחסנית.
* המצב הפנימי שלו (שם המצב + מצב המחסנית).
לאחר שהחליט, הוא עובר למצב פנימי חדש (לא בהכרח אחר), תוך כדי שינוי תוכן המחסנית, באחד משלושה אופנים:
* הוצאת אות אחת בלבד מראש המחסנית (ב[[אנגלית]], פעולת Pop).
שורה 28:
*<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>\ \Gamma^*=\Gamma\cup\left\{\varepsilon\right\}</math>).
*<math>\ q_0</math> הוא המצב ההתחלתי (ממנו מתחיל החישוב) <math>\ q_0\isin Q</math>.
*<math>\ \dashv</math> היא האות ההתחלתית שבמחסנית - תמיד! זוהי אות שמורה מיוחדת, שמשמעותה בפועל היא שהמחסנית ריקה, כי למחסנית ריקה באמת יש משמעות מעשית אחרת באוטומט מחסנית.
שורה 35:
משמעותה של פונקציית המעברים היא זו – בהינתן:
* המצב הנוכחי של האוטומט (שם המצב),
* האות הבאה שהוא קורא מהקלט (או [[מחרוזת ריקה (תכנות)|המילה הריקה]] <math>\ \varepsilon</math>, אם רוצים לתאר מעבר, שאינו כולל קריאת מילה מהקלט),
* האות שמופיעה בראש המחסנית,
* האות הבאה שהוא קורא מהקלט (או [[מחרוזת ריקה (תכנות)|המילה הריקה]] <math>\ \varepsilon</math>, אם רוצים לתאר מעבר, שאינו כולל קריאת מילה מהקלט),
פעולת האוטומט תהיה לעבור למצב אחר (או להישאר במצב שבו הוא נמצא), ולשנות את תוכן המחסנית על ידי הסרת האות שנמצאת בראש המחסנית והכנסת אות או מילה חדשה במקומה למחסנית (ייתכן, אפילו, להכניס את אותה האות שהוצאה, על-מנת לא לשנות את מצב המחסנית).
 
שורה 43:
פונקציית המעברים [[תחום הגדרה|אינה מוגדרת]], כאשר המחסנית ריקה. על כן, ריקון של המחסנית לפני תום קריאת מלוא מילת הקלט גורר בהכרח "היתקעות" של האוטומט ודחיית המילה הנקראת (כלומר, החזרת התשובה, שהמילה אינה בשפה שהאוטומט מזהה). באופן דומה, אין הכרח להגדיר את פונקציית המעברים עבור כל השלשות הסדורות האפשריות, וניתן לחשוב על כל שלשה סדורה, שעבורה הפונקציה אינה מוגדרת, כאילו היא "תוקעת" את האוטומט (כזכור, אנו מדברים על אוטומט (מחסנית) לא דטרמיניסטי).
 
להלן מספר דוגמאות לפעולת פונקציית המעברים <math>\ \delta</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>\ Z</math> למחסנית) ומהווה את ראש המחסנית החדש.
===תיאור חישוב===
על מנת לתאר חישובים באמצעות אוטומט מחסנית, נהוג להשתמש ב'''תיאור רגעי'''. תיאור רגעי הוא שלשה סדורה, שמכילה את כל המידע הרלוונטיהנחוץ לחישוב הצעד הנוכחי (והצעדים הנותרים) של האוטומט -:
* המצב בוהנוכחי הואשל נמצאהאוטומט (שם המצב),
* הקלטשארית שעודמילת נותרהקלט לו(החלק לקרואשטרם נקרא),
* ותוכןמצב המחסנית. המלא.
בצורה פורמלית, מגדירים תיאור רגעי בתור השלשה הסדורה <math>\ \left(q,w,\gamma\right)</math>, כך ש-:
* <math>\ q\in Q</math> הוא המצב הנוכחי,
* <math>\ w\in\Sigma^*</math> היא מילת הקלט שטרם נקראה (הערה: <math>\ \Sigma^*=\Sigma\cup\left\{\varepsilon\right\}</math>),
* ו-<math>\ \gamma\in\Gamma^*</math> הוא תוכנהתוכנהּ הנוכחי של המחסנית.
באמצעות תיאורים רגעיים, ניתן להציג חישוב של אוטומט מחסנית כסדרה של תיאורים רגעיים, שהמעבר בין כל שניים מהם מייצג צעד חישוב אחד של האוטומט. בצורה פורמלית, נהוג לסמן: <math>\ \left(q,aw,Z\alpha\right)\vdash\left(p,w,\beta\alpha\right)</math>,כדי לתאר מעבר מהמצב הרגעי <math>\ (q,aw,Z\alpha)</math> למצב הרגעי <math>\ \left(p,w,\beta\alpha\right)</math>. מעבר כזה הוא אפשרי [[אם ורק אם]] <math>\ (p,\beta)\in\delta(q,a,Z)</math> (כאן, ייתכן ש-<math>\ a\in\Sigma^*</math>, אוולכן ייתכן גם ש- <math>\ a=\varepsilon</math>).
 
באמצעות תיאורים רגעיים ניתן להציג חישוב של אוטומט מחסנית כסדרה של תיאורים רגעיים, שהמעבר בין כל שניים מהם מייצג צעד חישוב אחד של האוטומט. בצורה פורמלית נהוג לסמן
 
<math>\ \left(q,aw,Z\alpha\right)\vdash\left(p,w,\beta\alpha\right)</math>
 
כדי לתאר מעבר מהמצב הרגעי <math>\ (q,aw,Z\alpha)</math> למצב הרגעי <math>\ \left(p,w,\beta\alpha\right)</math>. מעבר כזה הוא אפשרי אם ורק אם <math>\ (p,\beta)\in\delta(q,a,Z)</math> (כאן ייתכן ש-<math>\ a\in\Sigma^*</math> או <math>\ a=\varepsilon</math>).
 
בדומה, משתמשים בסימון <math>\ \vdash^k</math> כדי לתאר מעבר בן <math>\ k</math> צעדים בין שני תיאורים רגעיים, ובסימן <math>\ \vdash^*</math> כדי לסמן שני תיאורים רגעיים, שניתן להגיע מהאחד אל השני במספר כלשהו של צעדים.
 
===הגדרת קבלה===
בדומה לאוטומט סופי, גם באוטומט מחסנית ניתן להגדיר קבלה של מילה באמצעות קבוצה של מצבים מקבלים: האוטומט יקבל מילה, אם לאחר סיום קריאת המילה (וייתכן שגם ביצוע מספר מסעי אפסילון לאחריה(<math>\ \varepsilon</math>) לאחר מכן) האוטומט נמצא (עצר) במצב מקבל. עם זאת, קיימת דרך נוספת להגדיר קבלה עבור אוטומט מחסנית - קבלה באמצעות ריקון המחסנית. באופן קבלה זה, אומרים שהאוטומט קיבלמקבל מילה, אם לאחר סיום קריאת המילה (ושוב, ייתכן שגם ביצוע מספר מסעי אפסילון לאחריהלאחר מכן) המחסנית ריקה (כזכור, אם המחסנית מתרוקנת '''לחלוטין (כולל האות המיוחדת השמורה <math>\ \dashv</math>) במהלך''' חישוב, הדבר גורם ל"תקיעת" האוטומט).
 
בצורה פורמלית, השפה שמתקבלת על ידי הגעה למצב מקבל מוגדרת בתור:
שורה 67 ⟵ 69:
*<math>\ L_e(M)=\left\{w\in\Sigma^*|\exists p\in Q: \left(q_0,w,\dashv\right)\vdash^*\left( p,\varepsilon,\varepsilon\right)\right\}</math>
 
באופן כללי, יכול להיות ש- <math>\ L_f(M)\ne L_e(M)</math>,; כלומר, השפהשהשפה שאוטומטשהאוטומט מזהה על ידי הגעה למצב מקבל שונה מהשפה שהוא מזהה על ידי ריקון המחסנית. עם זאת, קיימת [[שקילות (מתמטיקה)|שקילות]] בין שני אופני הקבלה: אם שפה כלשהי <math>\ L</math> מזוהה על ידי הגעה למצב מקבל בידי אוטומט מחסנית כלשהו, קיים אוטומט מחסנית (לא בהכרח אותו אחד) שמזהה אותהאת השפה <math>\ L</math> על ידי ריקון המחסנית, ולהפך. כמובן, שניתן גם להגדיר את השפה שהאוטומט מקבל כ[[איחוד (מתמטיקה)|איחוד]] שתי דרכי הגדרות הקבלה: <math>\ L_f(M)\cup L_e(M)</math>.
 
== לקריאה נוספת ==