रैखिक बाध्य ऑटोमेटा
एक रैखिक बाउंड ऑटोमैटॉन एक बहु-ट्रैक गैर-नियतात्मक ट्यूरिंग मशीन है जिसमें कुछ बंधे हुए परिमित लंबाई के टेप होते हैं।
Length = function (Length of the initial input string, constant c)
यहाँ,
Memory information ≤ c × Input information
गणना निरंतर बाध्य क्षेत्र तक सीमित है। इनपुट वर्णमाला में दो विशेष प्रतीक होते हैं जो बाएं छोर मार्कर और दाएं छोर मार्कर के रूप में कार्य करते हैं, जिसका अर्थ है कि संक्रमण न तो बाएं छोर के बाईं ओर चलते हैं और न ही टेप के दाहिने छोर के दाईं ओर।
एक रेखीय बंधित ऑटोमेटोन को 8-ट्यूपल (Q, X, ed, q 0 , ML, MR,,, F) के रूप में परिभाषित किया जा सकता है , जहां -
Q राज्यों का एक समुच्चय है
X टेप वर्णमाला है
∑ इनपुट वर्णमाला है
q0 प्रारंभिक अवस्था है
ML बाएं छोर है
MRदायां छोर मार्कर है जहां M R ≠ M L है
δ एक संक्रमण फ़ंक्शन है जो प्रत्येक जोड़ी (राज्य, टेप प्रतीक) को मैप करता है (राज्य, टेप प्रतीक, लगातार 'c') जहां c 0 या +1 या -1 हो सकता है
F अंतिम राज्यों का सेट है
एक नियतात्मक रैखिक बाउंड ऑटोमेटन हमेशा होता है context-sensitive और खाली भाषा के साथ रैखिक बंधे ऑटोमेटन है undecidable.।