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

תוכן שנמחק תוכן שנוסף
שורה 73:
ובראש המחסנית האות <math>b</math>, אזי האוטומט שולף את האות העליונה במחסנית, כותב במקומה <math>c</math> ומשנה את המצב בהתאם למעבר. אין הכרח לכתוב/לשלוף מהמחסנית אות בכל מעבר: אם לא נכתב דבר למחסנית <math>c=\epsilon</math>, ואם לא נקרא (נשלף) דבר מהמחסנית אזי <math>b=\epsilon</math>.
 
כעת ניתן לנתח את פעילות המכונה. במעבר הראשון המכונה מכניסה את הסימן $ למחסיתלמחסנית, כדי לסמן את סופהּ (מודל זה מניח שבתחילת פעולה המכונה, המחסנית ריקה, ועל כן ראשית דבר מכניסים סימן מיוחד לסמל את קצה המחסנית). במצב B המכונה "מעתיקה" את הקלט אל תוך המחסנית. במצב C המכונה "מוציאה" סימנים מהמחסנית, ומשווה אותם לקלט, המכונה ממשיכה הלאה רק אם הקלט זהה לתוכן המחסנית. לאחר מכן המכונה מוציאה את הסימן המיוחד $ ומסיימת.
 
לכן, אם הקלט מורכב משני חצאים, כאשר החצי השני שווה להיפוך-ראי החצי הראשון, המכונה תקבל את הקלט (כיוון שהכנסת החלק הראשון למחסנית "הופך" את הסדר, כלומר החצי השני חייב להיות הפוך מהקלט שהוכנס למחסנית.) באופן פורמלי, המכונה מכריעה את השפה של הפולינדרומים מאורך זוגי: