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

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