לדלג לתוכן

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

נוספו 3,132 בתים ,  לפני 6 שנים
שמירת ביניים (כלל הערך, עד פסקת "תיאור חישוב"): קישורים פנימיים, תיקון, עריכה והגהה, ועוד (שיפור הקריאות, והורדת סף הידע המקדים הנדרש לקריאה).
(שמירת ביניים (כלל הערך, עד פסקת "תיאור חישוב"): קישורים פנימיים, תיקון, עריכה והגהה, ועוד (שיפור הקריאות, והורדת סף הידע המקדים הנדרש לקריאה).)
[[תמונה:Automateapile.png|ממוזער|250px|ייצוג גרפי של אוטומט מחסנית, באמצעות [[גרף מכוון]]. האוטומט מורכב מ-4 [[מצב (מדעי המחשב)|מצבים]]: 2 מצבים מקבלים (מסומנים בעיגול כפול) ו-2 מצבים שאינם מקבלים (מסומנים בעיגול בודד).]]
[[תמונה:Automateapile.png|שמאל|ממוזער|250px|דוגמה לאוטומט מחסנית]]
ב[[מדעי המחשב]], '''אוטומט מחסנית''' הוא [[מודל חישובי]], שמהווה הרחבה של [[מודל מתמטי|מודל]] ה[[אוטומט סופי דטרמיניסטי|האוטומטאוטומט הסופי]] הדטרמיניסטי(ה[[אוטומט סופי דטרמיניסטי|דטרמיניסטי]]), על ידי הוספת [[מחסנית (מבנה נתונים)|מחסנית]], שבה האוטומט מסוגל לאכסןלאחסן [[נתונים|מידע]] (משמע, לאוטומט יש יכולת זיכרון). ההרחבה מגדילה את [[חישוביות|כוחו החישובי]] של האוטומט,; כלומר, את מחלקת[[קבוצה (מתמטיקה)|קבוצת]] ה[[שפה פורמלית|שפות]] שהוא מסוגל לזהות;. בגרסתו הסטנדרטית, מודל אוטומט המחסנית מסוגל לזהות בדיוק את כל [[שפה חסרת הקשר|השפות חסרות ההקשר]].
 
==תיאור לא פורמלי==
בדומה לאוטומט הסופי הדטרמיניסטי, אוטומט המחסנית מורכב מאוסף של '''[[מצב (מדעי המחשב)|מצבים]]''', המקבילים למצבי הזיכרון בהם יכוליכולה להימצא מחשבמכונת בזמןהחישוב ביצועבמהלך תוכניתביצוע מחשבחישוב. דרך הפעולה של האוטומט מבוססת על קריאת מילת [[קלט]] ([[מחרוזת (מדעי המחשב)|מחרוזת]], המורכבת מאלפבית סופי וידוע מראש) באופן סדרתי, אות אחת בכל פעם, עד אשר מסתיימת קריאת המילה, ואז מחזיר האוטומט תשובה - האם המילה שנקראה שייכת לשפהל[[שפה פורמלית|שפה]] אותה מזהה האוטומט, או לא.
 
ההבדל המרכזי שבין [[אוטומט סופי]] ובין אוטומט מחסנית הוא התקן הזיכרון הנוסף, שעומד לרשות אוטומט המחסנית - מחסנית, שמאפשרת אחסון (שמירת) [[נתונים]]. המחסנית מאחסנת אותיות (מעל אלפבית סופי וידוע מראש, אך לא בהכרח האלפבית שממנו בנויה מילת הקלט) בצורה סדרתית, כך שהאות האחרונה שהוכנסה למחסנית נמצאת בראשה, אחריה האות שהוכנסה לפניה למחסנית, וכן הלאה, עד האות הראשונה שהוכנסה למחסנית, הנמצאת בתחתיתה (ונגישה להצצה או שליפה אחרונה מכולן) (שיטת [[LIFO]]). בצורה זו, הגישה לזיכרון מוגבלת מאוד - ניתן לראות בכל פעם רק את האות שבראש המחסנית, וכדי לראות אות שבתוך המחסנית, יש להוציא מהמחסנית את כל האותיות שמעליה (ובכך "לאבד" אותן, שכן אין מקום אחסון נוסף עבורן).
 
=== ביצוע חישוב ===
בכל צעד [[חישוב (מדעי המחשב)|חישוב]] שלו, אוטומט המחסנית מחליט על דרך הפעולה שלו בהתבסס של שלושה נתונים - האות שהוא קורא מהקלט (אם כי הוא אינו מחויב לקרוא אות מהקלט בכל צעד), האות שנמצאת בראש המחסנית, והמצב הפנימי שלו. לאחר שהחליט, הוא עובר למצב פנימי אחר, ומשנה את תוכן המחסנית באופן מסוים - הוא יכול להוציא מהמחסנית את האות שבראשה, ולדחוף לתוכה במקומה אותיות אחרות.
בכל צעד [[חישוב (מדעי המחשב)|חישוב]] שלו, אוטומט המחסנית מחליט על דרך הפעולה שלו, בהתבסס על שלושה נתונים:
 
* האות שהוא קורא מהקלט (אם כי הוא אינו מחויב לקרוא אות מהקלט בכל צעד).
המודל הסטנדרטי של אוטומט המחסנית הוא [[אי דטרמיניזם|אי דטרמיניסטי]] - בכל צעד חישוב האוטומט מסוגל לבצע מספר בחירות שונות, ולכן ניתן לתאר חישובים שונים רבים שהוא מבצע על כל מילת קלט, ודי בכך שבחישוב אחד האוטומט יכריע כי מילת הקלט שייכת לשפה אותה הוא מזהה. ניתן להגדיר גם מודל דטרמיניסטי של אוטומט מחסנית, אך מתברר כי מודל זה הוא בעל יכולת חישובית פחותה ממש מזו של המודל האי דטרמיניסטי - קיימות שפות אותן המודל האי דטרמיניסטי מסוגל לזהות והמודל הדטרמיניסטי לא. בכך נבדל אוטומט המחסנית הן מהאוטומט הסופי והן ממודל החישוב הכללי יותר, של [[מכונת טיורינג]] - בשני המודלים הללו מתקיימת שקילות מבחינת כוח החישוב בין המודל הדטרמיניסטי ובין המודל האי דטרמיניסטי.
* האות שנמצאת בראש המחסנית.
* המצב הפנימי שלו (שם המצב + מצב המחסנית).
לאחר שהחליט, הוא עובר למצב פנימי חדש (לא בהכרח אחר), תוך כדי שינוי תוכן המחסנית, באחד משלושה אופנים:
* הוצאת אות אחת בלבד מראש המחסנית (ב[[אנגלית]], פעולת Pop).
* אי-ביצוע כל שינוי במחסנית (לא הכנסה ולא הוצאה של אותיות; משמע, רק "הצצנו"/הסתכלנו על האות שבראש המחסנית).
* דחיפת (הכנסת) לתוכה במקומה אותיות אחרות (באנגלית, פעולת Push).
המודל הסטנדרטי של אוטומט המחסנית הוא [[אי -דטרמיניזם|אי -דטרמיניסטי]] - בכל צעד חישוב, האוטומט מסוגל לבצע מספר בחירות שונות במקביל, ולכן, ניתן לתאר חישובים שונים רבים שהוא מבצע על כל מילת קלט, ודי בכך, שבחישובשבאחד אחדהחישובים האוטומט יכריע כי מילת הקלט שייכת לשפה אותה הוא מזהה (כלומר, יסיים את חישובו במצב מקבל). ניתן להגדיר גם מודל [[דטרמיניזם|דטרמיניסטי]] של אוטומט מחסנית, אך מתברר כי מודל זה הוא בעל יכולת חישובית פחותה ממש מזו של המודל האי -דטרמיניסטי -: קיימות שפות, אותן המודל האי -דטרמיניסטי מסוגל לזהות והמודל הדטרמיניסטי לא. בכך נבדל אוטומט המחסנית הן מהאוטומט הסופי והן ממודל החישוב הכללי יותר, של [[מכונת טיורינג]] - בשני המודלים הללו מתקיימת [[שקילות (מתמטיקה)|שקילות]], מבחינת [[חישוביות|כוח החישוב]], בין המודל הדטרמיניסטי ובין המודל האי -דטרמיניסטי.
 
==תיאור פורמלי==
{{סימון מתמטי}}[[מודל מתמטי|תיאור מתמטי פורמלי]] של אוטומט מחסנית <math>\ A</math> הוא באמצעות השביעייהה[[N-יה סדורה|שביעייה הסדורה]] הבאה:
 
<math>\ A=\left\{Q,\Sigma,\Gamma,\delta,q_0,\dashv,F\right\}</math>
כאשר:
 
*<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>\ F\subseteq Q</math> היא קבוצת המצבים המקבלים.
 
משמעותה של פונקציית המעברים היא זו – בהינתן:
משמעותה של פונקציית המעברים היא זו: בהינתן המצב הנוכחי של האוטומט, האות הבאה שהוא קורא מהקלט (או המילה הריקה <math>\ \varepsilon</math> אם רוצים לתאר מעבר שאינו כולל קריאת מילה מהקלט) והאות שמופיעה בראש המחסנית, פעולת האוטומט תהיה לעבור למצב אחר (או להישאר במצב שבו היה קודם) ולשנות את תוכן המחסנית על ידי הסרת האות שנמצאת בראש המחסנית והכנסת מילה חדשה למחסנית במקומה.
* המצב הנוכחי של האוטומט (שם המצב),
* האות שמופיעה בראש המחסנית,
* האות הבאה שהוא קורא מהקלט (או [[מחרוזת ריקה (תכנות)|המילה הריקה]] <math>\ \varepsilon</math>, אם רוצים לתאר מעבר, שאינו כולל קריאת מילה מהקלט),
פעולת האוטומט תהיה לעבור למצב אחר (או להישאר במצב שבו הוא נמצא), ולשנות את תוכן המחסנית על ידי הסרת האות שנמצאת בראש המחסנית והכנסת אות או מילה חדשה במקומה למחסנית (ייתכן, אפילו, להכניס את אותה האות שהוצאה, על-מנת לא לשנות את מצב המחסנית).
 
מכיוון שהאוטומט אי -דטרמיניסטי, לכל שלשה סדורה של: מצב, + אות קלט ואות+ אות מראש המחסנית, [[יחס|מותאמת]] '''[[קבוצה''' (מתמטיקה)|קבוצה]] של זוגות סדורים אפשריים, שלשכל מצבאחד מהם מורכב מ: המצב שאליו עוברים ואות+ האות שמוכנסת לראש המחסנית (יכולה להיות גם האות/המילה הריקה <math>\ \varepsilon</math>; דהינו, לא להכניס אף אות למחסנית). לכן, [[טווח של פונקציה|טווח פונקציית]] המעברים הוא <math>\ \mathrm{P}\left(Q\times\Gamma^*\right)</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> הוא תוכנה הנוכחי של המחסנית.