אוטומטים ושפות פורמליות/אוטומט מחסנית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 73:
ובראש המחסנית האות <math>b</math>, אזי האוטומט שולף את האות העליונה במחסנית, כותב במקומה <math>c</math> ומשנה את המצב בהתאם למעבר. אין הכרח לכתוב/לשלוף מהמחסנית אות בכל מעבר: אם לא נכתב דבר למחסנית <math>c=\epsilon</math>, ואם לא נקרא (נשלף) דבר מהמחסנית אזי <math>b=\epsilon</math>.
כעת ניתן לנתח את פעילות המכונה. במעבר הראשון המכונה מכניבה את הסימן $ למחסית, כדי לסמן את סופה (מודל זה מניח שבתחילת פעולה המכונה, המחסנית ריקה, ועל כן ראשית דבר מכניסים סימן מיוחד לסמל את קצה המחסנית). במצב B המכונה "מעתיקה" את הקלט אל תוך המחסנית. במצב C המכונה "מוציאה" סימנים מהמחסנית, ומשווה אותם לקלט, המכונה ממשיכה הלאה רק אם הקלט זהה לתוכן המחסנית. לאחר מכן המכונה מוצאיה את הסימן המיוחד $ ומסיימת.
לכן, אם הקלט מורכב משני חצאים, כאשר החצי השני שווה להיפוך-ראי החצי הראשון, המכונה תקבל את הקלט (כיוון שהכנסת החלק הראשון למחסנית "הופך" את הסדר, כלומר החצי השני חייב להיות הפוך מהקלט שהוכנס למחסנית.) באופן פורמלי, המכונה מכריעה את השפה של הפולינדרומים מאורך זוגי:
<center><math>L= \{ww^R \mid w\in \{0,1\}^*\}</math></center>
בדוגמא גם ניתן לראות את כוחה של אי-הדטרמיניסטיות. המכונה "מנחשת" מתי לעבור מהחלק שמכניס את החצי הראשון למחסנית (מצב B) לחלק שבודק את החצי השני (מצב C). מאידך, אם הקלט לא בנוי בצורה האמורה, כל ניחוש לא יצליח.
{{אוטומטים ושפות פורמליות|מוגבל}}
| |||