אוטומט חסום ליניארית

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

במדעי המחשב, אוטומט חסום ליניארית או LBA (ראשי תיבות של: Linear Bounded Automaton) הוא מכונת טיורינג לא-דטרמיניסטית המקיימת את שלושת התנאים הבאים:

  • אלף-בית הקלט כולל שני סימנים מיוחדים, לסימון הקצה השמאלי והקצה הימני.
  • אין להדפיס סימנים אחרים משני הסימנים שבתנאי הראשון באחד מהקצוות.
  • קבוצת המעברים אינם יכולים להכיל מעברים שמאלה מהסמן השמאלי או ימינה מהסמן הימני.[1]

במילים אחרות: במקום סרט אינסופי עבור הקלט (כפי שיש במכונת טיורינג רגילה) סרט הקלט הוא סופי ומכיל את הקלט עצמו ושני סימני הקצה.

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

LBA ושפות תלויות הקשר[עריכת קוד מקור | עריכה]

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

בעיות LBA [עריכת קוד מקור | עריכה]

בפרסום המדעי שלו בשנת 1960, ציין פרופסור קורודה (Sige-Yuki Kuroda) שני אתגרים מחקריים, אשר לאחר מכן נתפרסמו כ "בעיות ה-LBA".

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

בעיית LBA הראשונה: האם

בעיית ה-LBA השנייה היא האם המחלקה של השפות המתקבלות על ידי LBA סגורה תחת משלים.

בעיית ה-LBA השנייה: האם

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ John E. Hopcroft; Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X.