אוטומט מחסנית

מתוך ויקיפדיה, האנציקלופדיה החופשית

ערך זה זקוק לעריכה, על מנת שיתאים לסגנון המקובל בוויקיפדיה.
הסיבה שניתנה לכך היא מפוזר למדי ולוקה בחסר. אם אתם סבורים כי אין בדף בעיה, ניתן לציין זאת בדף השיחה שלו.

אוטומט מחסנית, הינו שיכלול של האוטומט הסופי הדרמיניסטי הפשוט. יתרונו, ובכך גם כוחו על פני האס"ד הינו קיבולת הזיכרון האינסופית שלו. כל זאת, בזכות שהאוטומט משתמש במחסנית [=מבנה נתונים המאפשר שמירת איברים ללא הגבלה]. כך, לשפות מסוימות שאינן רגולריות, דהיינו שלא ניתן לבנות להן אס"ד, נוכל לבנות להן אוטומט מחסנית. שפות כאלה, נקראות "שפות חופשיות-הקשר". כך, לדוגמה, לשפה: anbn לא ניתן לבנות אס"ד- עקב הצורך בשמירה של אינסוף איברים, ובכך גם צורך בזכרון לא מוגבל. אולם, לשפה ניתן לבנות אוטומט מחסנית פשוט למדי, ולכן השפה היא שפה "חופשית הקשר".

כל שפה רגולרית הינה שפה חופשית הקשר, שכן באופן עקרוני, ניתן לבנות לכל שפה רגולרית אוטומט מחסנית [למרות שהמחסנית לא תהיה בשימוש כלל].

חרף יתרונותיו הרבים, גם לאוטומט המחסנית חסרונות. כך, לדוגמה, עקב השתמשותו במחסנית, ניתן רק לדחוף איברים לתוכה או לשלוף איברים ממנה, וכך אי אפשר לשחזר את האיבר שכבר נשלף.

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