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

נוספו 104 בתים ,  לפני 5 שנים
ויקיזציה הוספת קישור לערך אוטומט סופי לא דטרמיניסטי
(ההבדל בין SIGMA* לבין SIGMA union {epsilon}‎ - הראשון הוא קבוצת כל המילים מעל SIGMA, השני הוא קבוצת האותיות + המילה הריקה (ראו במקורות ובוויקיפדיה האנגלית))
(ויקיזציה הוספת קישור לערך אוטומט סופי לא דטרמיניסטי)
פעולת האוטומט תהיה לעבור למצב אחר (או להישאר במצב שבו הוא נמצא), ולשנות את תוכן המחסנית על ידי הסרת האות שנמצאת בראש המחסנית והכנסת אות או מילה חדשה במקומה למחסנית (ייתכן, אפילו, להכניס את אותה האות שהוצאה, על-מנת לא לשנות את מצב המחסנית).
 
מכיוון שהאוטומטש[[אוטומט סופי לא דטרמיניסטי|האוטומט אי-דטרמיניסטי]], לכל שלשה סדורה של: מצב + אות קלט + אות מראש המחסנית, [[יחס|מותאמת]] [[קבוצה (מתמטיקה)|קבוצה]] של זוגות סדורים אפשריים, שכל אחד מהם מורכב מ: המצב שאליו עוברים + המילה שמוכנסת לראש המחסנית (יכולה להיות גם המילה הריקה <math>\ \varepsilon</math>; דהינו, לא להכניס אף אות למחסנית). לכן, [[טווח של פונקציה|טווח פונקציית]] המעברים הוא <math>\ \mathrm{P}\left(Q\times\Gamma^*\right)</math> – [[קבוצת החזקה]] של כל הזוגות האפשריים של מצב + המילה המוכנסת לראש המחסנית. עם זאת, מניחים כי רק [[תת-קבוצה|תת-הקבוצות]] [[קבוצה סופית|הסופיות]] של זוגות שכאלו יכולים להתקבל באמצעות פונקציית המעברים (כלומר, מספר דרכי הפעולה השונות של האוטומט, בהינתן מצב, אות קלט ואות מראש המחסנית הוא סופי).
 
פונקציית המעברים [[תחום הגדרה|אינה מוגדרת]], כאשר המחסנית ריקה. על כן, ריקון של המחסנית לפני תום קריאת מלוא מילת הקלט גורר בהכרח "היתקעות" של האוטומט ודחיית המילה הנקראת (כלומר, החזרת התשובה, שהמילה אינה בשפה שהאוטומט מזהה). באופן דומה, אין הכרח להגדיר את פונקציית המעברים עבור כל השלשות הסדורות האפשריות, וניתן לחשוב על כל שלשה סדורה, שעבורה הפונקציה אינה מוגדרת, כאילו היא "תוקעת" את האוטומט (כזכור, אנו מדברים על אוטומט (מחסנית) [[אוטומט סופי לא דטרמיניסטי|לא דטרמיניסטי]]).
 
להלן מספר דוגמאות לפעולת פונקציית המעברים <math>\ \delta</math> (הפועלת על שלשה סדורה ומחזירה זוג סדור), שבכולן האוטומט מתחיל במצב <math>\ q</math> ונשאר בו:
84

עריכות