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

הוסר בית אחד ,  לפני 11 שנים
מ (בוט מוסיף: nl:Stapelautomaat)
משמעותה של פונקציית המעברים היא זו: בהינתן המצב הנוכחי של האוטומט, האות הבאה שהוא קורא מהקלט (או המילה הריקה <math>\ \varepsilon</math> אם רוצים לתאר מעבר שאינו כולל קריאת מילה מהקלט) והאות שמופיעה בראש המחסנית, פעולת האוטומט תהיה לעבור למצב אחר (או להישאר במצב שבו היה קודם) ולשנות את תוכן המחסנית על ידי הסרת האות שנמצאת בראש המחסנית והכנסת אות חדשה למחסנית במקומה.
 
מכיוון שהאוטומט אי דטרמיניסטי, לכל שלשה של מצב, אות קלט ואות מראש המחסנית מותאמת '''קבוצה''' של זוגות אפשריים של מצב שאליו עוברים ומילהואות שמוכנסת לראש המחסנית. לכן טווח פונקציית המעברים הוא <math>\ \mathrm{P}\left(Q\times\Gamma^*\right)</math> - [[קבוצת החזקה]] של כל הזוגות האפשריים. עם זאת, מניחים כי רק תת-הקבוצות '''הסופיות''' של זוגות שכאלו יכולים להתקבל באמצעות פונקציית המעברים (כלומר, מספר דרכי הפעולה השונות של האוטומט בהינתן מצב, אות קלט ואות מראש המחסנית הוא סופי).
 
פונקציית המעברים אינה מוגדרת כאשר המחסנית ריקה; על כן, ריקון של המחסנית לפני תום קריאת הקלט גורר בהכרח "היתקעות" של האוטומט ודחיית המילה הנקראת. באופן דומה, אין הכרח להגדיר את פונקציית המעברים עבור כל השלשות האפשריות, וניתן לחשוב על כל שלשה שעבורה הפונקציה אינה מוגדרת כאילו היא "תוקעת" את האוטומט.
 
באופן כללי יכול להיות ש-<math>\ L_f(M)\ne L_e(M)</math>, כלומר השפה שאוטומט מזהה על ידי הגעה למצב מקבל שונה מהשפה שהוא מזהה על ידי ריקון המחסנית. עם זאת, קיימת שקילות בין שני אופני הקבלה: אם שפה כלשהי <math>\ L</math> מזוהה על ידי הגעה למצב מקבל בידי אוטומט מחסנית כלשהו, קיים אוטומט מחסנית (לא בהכרח אותו אחד) שמזהה אותה על ידי ריקון המחסנית, ולהפך.
 
== לקריאה נוספת ==
* {{פא"ר|מספר=93|שם הספר=אוטומטים ושפות פורמליות|כותב=שמואל זקס ונסים פרנסיז|שנה=2000}}
משתמש אלמוני