אוטומט מחסנית – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
שורה 26:
*<math>\ F\subseteq Q</math> היא קבוצת המצבים המקבלים.
משמעותה של פונקציית המעברים היא זו: בהינתן המצב הנוכחי של האוטומט, האות הבאה שהוא קורא מהקלט (או המילה הריקה <math>\ \varepsilon</math> אם רוצים לתאר מעבר שאינו כולל קריאת מילה מהקלט) והאות שמופיעה בראש המחסנית, פעולת האוטומט תהיה לעבור למצב אחר (או להישאר במצב שבו היה קודם) ולשנות את תוכן המחסנית על ידי הסרת האות שנמצאת בראש המחסנית והכנסת
מכיוון שהאוטומט אי דטרמיניסטי, לכל שלשה של מצב, אות קלט ואות מראש המחסנית מותאמת '''קבוצה''' של זוגות אפשריים של מצב שאליו עוברים ואות שמוכנסת לראש המחסנית. לכן טווח פונקציית המעברים הוא <math>\ \mathrm{P}\left(Q\times\Gamma^*\right)</math> - [[קבוצת החזקה]] של כל הזוגות האפשריים. עם זאת, מניחים כי רק תת-הקבוצות '''הסופיות''' של זוגות שכאלו יכולים להתקבל באמצעות פונקציית המעברים (כלומר, מספר דרכי הפעולה השונות של האוטומט בהינתן מצב, אות קלט ואות מראש המחסנית הוא סופי).
| |||