אוטומטים ושפות פורמליות/אוטומט מחסנית: הבדלים בין גרסאות בדף

המודל הסטנדרטי של אוטומט המחסנית הוא '''אי דטרמיניסטי''' - בכל צעד חישוב האוטומט מסוגל לבצע מספר בחירות שונות, ולכן ניתן לתאר חישובים שונים רבים שהוא מבצע על כל מילת קלט, ודי בכך שבחישוב אחד האוטומט יכריע כי מילת הקלט שייכת לשפה אותה הוא מזהה. ניתן להגדיר גם מודל דטרמיניסטי של אוטומט מחסנית, אך מתברר כי מודל זה הוא בעל יכולת חישובית פחותה ממש מזו של המודל האי דטרמיניסטי - קיימות שפות אותן המודל האי דטרמיניסטי מסוגל לזהות והמודל הדטרמיניסטי לא. בכך נבדל אוטומט המחסנית מן האוטומט הסופי (אס"ד/אסל"ד), בו (באוטומט הסופי) קיימת שקילות מבחינת כוח החישוב בין המודל הדטרמיניסטי ובין המודל האי דטרמיניסטי, ואילו באוטומט המחסנית אינה קיימת שקילות בין המודל הדטרמיניסטי והאי-דטרמיניסטי כאמור.