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