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

נוספו 31 בתים ,  לפני 4 שנים
ויקישיתוף בשורה
(ויקיזציה הוספת קישור לערך אוטומט סופי לא דטרמיניסטי)
(ויקישיתוף בשורה)
[[תמונהקובץ:Automateapile.png|ממוזער|250px|ייצוג גרפי של אוטומט מחסנית, באמצעות [[גרף מכוון]]. האוטומט מורכב מ-4 [[מצב (מדעי המחשב)|מצבים]]: 2 מצבים מקבלים (מסומנים בעיגול כפול) ו-2 מצבים שאינם מקבלים (מסומנים בעיגול בודד).]]
ב[[מדעי המחשב]], '''אוטומט מחסנית''' הוא [[מודל חישובי]], שמהווה הרחבה של [[מודל מתמטי|מודל]] ה[[אוטומט סופי|אוטומט הסופי]] (ה[[אוטומט סופי דטרמיניסטי|דטרמיניסטי]]), על ידי הוספת [[מחסנית (מבנה נתונים)|מחסנית]], שבה האוטומט מסוגל לאחסן [[נתונים|מידע]] (משמע, לאוטומט יש יכולת זיכרון). ההרחבה מגדילה את [[חישוביות|כוחו החישובי]] של האוטומט; כלומר, את [[קבוצה (מתמטיקה)|קבוצת]] ה[[שפה פורמלית|שפות]] שהוא מסוגל לזהות. בגרסתו הסטנדרטית, מודל אוטומט המחסנית מסוגל לזהות בדיוק את כל [[שפה חסרת הקשר|השפות חסרות ההקשר]].
 
פעולת האוטומט תהיה לעבור למצב אחר (או להישאר במצב שבו הוא נמצא), ולשנות את תוכן המחסנית על ידי הסרת האות שנמצאת בראש המחסנית והכנסת אות או מילה חדשה במקומה למחסנית (ייתכן, אפילו, להכניס את אותה האות שהוצאה, על-מנת לא לשנות את מצב המחסנית).
 
מכיוון ש[[אוטומט סופי לא דטרמיניסטי|האוטומט אי-דטרמיניסטי]], לכל שלשה סדורה של: מצב + אות קלט + אות מראש המחסנית, [[יחס|מותאמת]] [[קבוצה (מתמטיקה)|קבוצה]] של זוגות סדורים אפשריים, שכל אחד מהם מורכב מ: המצב שאליו עוברים + המילה שמוכנסת לראש המחסנית (יכולה להיות גם המילה הריקה <math>\ \varepsilon</math>; דהינו, לא להכניס אף אות למחסנית). לכן, [[טווח של פונקציה|טווח פונקציית]] המעברים הוא <math>\ \mathrm{P}\left(Q\times\Gamma^*\right)</math> – [[קבוצת החזקה]] של כל הזוגות האפשריים של מצב + המילה המוכנסת לראש המחסנית. עם זאת, מניחים כי רק [[תת-קבוצה|תת-הקבוצות]] [[קבוצה סופית|הסופיות]] של זוגות שכאלו יכולים להתקבל באמצעות פונקציית המעברים (כלומר, מספר דרכי הפעולה השונות של האוטומט, בהינתן מצב, אות קלט ואות מראש המחסנית הוא סופי).
 
פונקציית המעברים [[תחום הגדרה|אינה מוגדרת]], כאשר המחסנית ריקה. על כן, ריקון של המחסנית לפני תום קריאת מלוא מילת הקלט גורר בהכרח "היתקעות" של האוטומט ודחיית המילה הנקראת (כלומר, החזרת התשובה, שהמילה אינה בשפה שהאוטומט מזהה). באופן דומה, אין הכרח להגדיר את פונקציית המעברים עבור כל השלשות הסדורות האפשריות, וניתן לחשוב על כל שלשה סדורה, שעבורה הפונקציה אינה מוגדרת, כאילו היא "תוקעת" את האוטומט (כזכור, אנו מדברים על אוטומט (מחסנית) [[אוטומט סופי לא דטרמיניסטי|לא דטרמיניסטי]]).
 
==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* {{לא מדויק|2015/03/22/pushdown_automata}}