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..