אוטומטים ושפות פורמליות/אוטומט מחסנית: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
Gran (שיחה | תרומות)
שורה 14:
 
==תיאור פורמלי==
קיימים מספר מודלים שקולים לתיאור אוטומט מחסנית.
* מודל ריקון המחסנית: במודל זה האוטומט מתחיל כשבמחסנית יש תו מיוחד. ברגע שמרוקנים את המחסנית (אם הקלט הסתיים) המילה מתקבלת על-ידי המכונה.
* מוגל מצבים מקבלים: מודל זה דומה למודל האוטומט הסופי - מילה מתקבלת אם סיום עיבוד המילה הוא במצה סופי, ללא קשר למצב המחסנית.
ההגדרה הפורמלית, לפיכך, יכולה להכיל תיאור של מצבים מקבלים <math>F</math>, או לא להכילה. כמו כן התיאור יכו להכיל את התו המיוחד הקיים במחסנית, או לא להגדירו, בהתאם למודל הרצוי. אנחנו נשתמש בתיאור המכיל את כל הרכיבים, כך שניתן להגדיר את מודל החישוב הרצוי בשתי הדרכים לעיל.
 
תיאור מתמטי פורמלי של אוטומט מחסנית <math>\ A</math> הוא באמצעות השביעייה הבאה:
 
שורה 23 ⟵ 28:
*<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^*\cup\{\varepsilon\})\right)</math> היא פונקציית המעברים.
*<math>\ q_0</math> הוא המצב ההתחלתי.
*<math>\ \dashv</math> היא האות ההתחלתית שבמחסנית.
שורה 30 ⟵ 35:
משמעותה של פונקציית המעברים היא זו: בהינתן המצב הנוכחי של האוטומט, האות הבאה שהוא קורא מהקלט (או המילה הריקה <math>\ \varepsilon</math> אם רוצים לתאר מעבר שאינו כולל קריאת מילה מהקלט) והאות שמופיעה בראש המחסנית, פעולת האוטומט תהיה לעבור למצב אחר (או להישאר במצב שבו היה קודם) ולשנות את תוכן המחסנית על ידי הסרת האות שנמצאת בראש המחסנית והכנסת מילה חדשה למחסנית במקומה.
 
מכיוון שהאוטומט אי דטרמיניסטי, לכל שלשה של מצב, אות קלט ואות מראש המחסנית מותאמת '''קבוצה''' של זוגות אפשריים של מצב שאליו עוברים ואות שמוכנסת לראש המחסנית. לכן טווח פונקציית המעברים הוא <math>\ \mathrm{P}\left(Q\times(\Gamma^*\cup\{\varepsilon\})\right )</math> - [[קבוצת החזקה]] של כל הזוגות האפשריים (כאשר אנחנו מאפשרים לא לכתוב כלום למחסנית, כלומר לכתוב <math>\varepsilon</math>). עם זאת, מניחים כי רק תת-הקבוצות '''הסופיות''' של זוגות שכאלו יכולים להתקבל באמצעות פונקציית המעברים (כלומר, מספר דרכי הפעולה השונות של האוטומט בהינתן מצב, אות קלט ואות מראש המחסנית הוא סופי).
 
פונקציית המעברים אינה מוגדרת כאשר המחסנית ריקה; על כן, ריקון של המחסנית לפני תום קריאת הקלט גורר בהכרח "היתקעות" של האוטומט ודחיית המילה הנקראת. באופן דומה, אין הכרח להגדיר את פונקציית המעברים עבור כל השלשות האפשריות, וניתן לחשוב על כל שלשה שעבורה הפונקציה אינה מוגדרת כאילו היא "תוקעת" את האוטומט.