אוטומט מחסנית – הבדלי גרסאות

* דחיפת (הכנסת) לתוכה במקומה אותיות אחרות (באנגלית, פעולת Push).

המודל הסטנדרטי של אוטומט המחסנית הוא [[אי-דטרמיניזם|אי-דטרמיניסטי]] – בכל צעד חישוב, האוטומט מסוגל לבצע מספר בחירות שונות במקביל, ולכן, ניתן לתאר חישובים שונים רבים שהוא מבצע על כל מילת קלט, ודי בכך, שבאחד החישובים האוטומט יכריע כי מילת הקלט שייכת לשפה אותה הוא מזהה (כלומר, יסיים את חישובו במצב מקבל). ניתן להגדיר גם מודל [[דטרמיניזם|דטרמיניסטי]] של אוטומט מחסנית, אך מתברר כי מודל זה הוא בעל יכולת חישובית פחותה ממש מזו של המודל האי-דטרמיניסטי: קיימות שפות, אותן המודל האי-דטרמיניסטי מסוגל לזהות ואילו המודל הדטרמיניסטי לא מסוגל לזהותן; דוגמה לשפה כזאת היא שפת כל ה[[פלינדרום|פלינדרומים]]. בכך נבדל אוטומט המחסנית הן מהאוטומט הסופי והן ממודל החישוב הכללי יותר, של [[מכונת טיורינג]] – בשני המודלים הללו מתקיימת [[שקילות (מתמטיקה)|שקילות]], מבחינת [[חישוביות|כוח החישוב]], בין המודל הדטרמיניסטי ובין המודל האי-דטרמיניסטי.

 

==תיאור פורמלי==