Otomat tuyến tính giới nội bộ (LBA)

Ta gọi Ôtômát tuyến tính giới nội (Linear Bounded Automata - LBA) là một máy Turing không đơn định và không có khả năng nới rộng vùng làm việc ra khỏi mút trái và mút phải của chuỗi nhập. Nó phải thỏa hai điều kiện sau :

1) Bộ chữ cái nhập của nó có chứa thêm hai ký hiệu đặc biệt  và $ dùng làm ký hiệu đánh dấu mút trái và mút phải.

2) LBA không thực hiện phép chuyển sang trái (L) từ  và không thực hiện phép chuyển sang phải (R) từ $, và cũng không viết các ký hiệu khác lên  và $.

LBA đơn giản là một máy Turing nhưng thay vì sử dụng một băng không giới hạn cho việc tính toán, nó bị hạn chế chỉ trong phạm vi băng chứa chuỗi nhập x với hai ô chứa các ký hiệu đánh dấu cận đầu mút. Sự giới hạn này làm cho việc tính toán phải thông qua một số các hàm tuyến tính trên độ dài chuỗi, do đó ta gọi mô hình này là ôtômát tuyến tính giới nội. LBA không dùng các ô trống ở trên băng về phía trái và phía phải của chuỗi nhập, vì vậy ký hiệu khoảng trắng B (Blank) như đã dùng ở máy Turing là không cần dùng ở đây. Trái lại, để LBA nhận biết được giới hạn bên trái và giới hạn bên phải của chuỗi nhập, ta phải đưa thêm vào bộ chữ cái nhập Σ hai ký hiệu đặc biệt , $ để đánh dấu mút trái và mút phải của chuỗi. Vậy, tại thời điểm bắt đầu, chuỗi nhập đưa vào ở trên băng sẽ có dạng  w $, trong đó w ∈ (- {, $})^* là chuỗi cần đoán nhận. Trong quá trình làm việc, khi đầu đọc đọc tới ô có chứa  hay $, thì phép chuyển tiếp theo sau đó chỉ có thể là đổi trạng thái, chuyển đầu đọc trở lại phía trong phạm vi băng (tức chuyển sang phải khi gặp  và chuyển sang trái khi gặp $), và không được phép viết ký hiệu gì khác trên băng tại ô đang đọc khi gặp  và $.

Định nghĩa LBA

Một cách hình thức, LBA là một hệ thống M(Q, Σ, Γ,δ,q_o,, $, F), trong đó các thành phần Q, Σ, Γ, q_o, F vẫn như đã định nghĩa ở máy Turing, còn , $ ∈ Σ và hàm chuyển :

δ: Q × Γ → (Q × Γ × { L, R})

phải thỏa mãn điều kiện:

• Nếu (p, Y, E) ∈ δ(q, ) thì Y =  và E = R
• Nếu (p, Y, E) ∈ δ(q, $) thì Y = $ và E = L

Ngôn ngữ được chấp nhận bởi LBA

Ta định nghĩa ngôn ngữ L(M) được đoán nhận bởi LBA M là tập hợp :

L(M) = { w | w ∈ (Σ - {, $})^* và q_ow$ ⊢M^* αqβ với q ∈ F và αβ ∈ Γ^* }

Chú ý rằng các ký hiệu đánh dấu hai đầu mút ngay từ hình thái bắt đầu chúng đã có mặt trên băng nhập, nhưng chúng không được xem như thuộc một phần của chuỗi được chấp nhận hay không được chấp nhận bởi LBA. Vì đầu đọc của LBA không thể dịch chuyển ra ngoài phần chuỗi nhập nên chúng ta không cần định nghĩa các khoảng trống (ký hiệu Blank) phía bên phải của $.