Dữ liệu tự động giới hạn tuyến tính
Một máy tự động có giới hạn tuyến tính là một máy Turing đa rãnh không xác định với một dải băng có độ dài hữu hạn nhất định.
Length = function (Length of the initial input string, constant c)
Đây,
Memory information ≤ c × Input information
Việc tính toán bị giới hạn trong vùng giới hạn không đổi. Bảng chữ cái đầu vào chứa hai ký hiệu đặc biệt dùng làm điểm đánh dấu cuối bên trái và điểm đánh dấu cuối bên phải có nghĩa là các chuyển đổi không di chuyển sang trái của điểm đánh dấu cuối bên trái cũng như sang phải của điểm đánh dấu cuối bên phải của băng.
Một automaton giới hạn tuyến tính có thể được định nghĩa là một bộ 8 (Q, X, ∑, q 0 , ML, MR, δ, F) trong đó -
Q là một tập hợp hữu hạn các trạng thái
X là bảng chữ cái băng
∑ là bảng chữ cái đầu vào
q0 là trạng thái ban đầu
ML là điểm đánh dấu cuối bên trái
MRlà điểm đánh dấu cuối bên phải nơi M R ≠ M L
δ là một hàm chuyển đổi ánh xạ từng cặp (trạng thái, biểu tượng băng) sang (trạng thái, biểu tượng băng, Hằng số 'c') trong đó c có thể là 0 hoặc +1 hoặc -1
F là tập hợp các trạng thái cuối cùng
Automaton giới hạn tuyến tính xác định luôn là context-sensitive và automaton giới hạn tuyến tính với ngôn ngữ trống là undecidable..