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

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

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

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

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

LBA ושפות תלויות הקשר

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

בעיות LBA

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

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

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

$?NSPACE(O(n))=DSPACE(O(n))$

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

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

$?NSPACE(O(n))=coNSPACE(O(n))$

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

קישורים חיצוניים

• Linear Bounded Automata מאת פורבס. ד. לואיס
• Linear Bounded Automata שקופיות, חלק מתשפות תלויות הקשר על ידי ארתור סי פלק
• Linear Bounded Automata, חלק מסילבוס "התאוריה של חישוביות", על ידי דוד מוטזסק