הבדלים בין גרסאות בדף "אוטומט מחסנית"

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