0.1 Ôtômát tuyến tính giới nội và văn phạm cảm ngữ cảnh

Ôtômát tuyến tính giới nội (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, , ,,qo,, $, F), trong đó các thành phần Q, , , qo, F vẫn như đã định nghĩa ở máy Turing, còn , $   và hàm chuyển :