Linear Bounded Automata
หุ่นยนต์ที่มีขอบเขตเชิงเส้นเป็นเครื่องทัวริงแบบไม่กำหนดทิศทางแบบหลายแทร็กพร้อมเทปที่มีความยาว จำกัด ขอบเขต
Length = function (Length of the initial input string, constant c)
ที่นี่
Memory information ≤ c × Input information
การคำนวณถูก จำกัด ไว้ที่พื้นที่ขอบเขตคงที่ ตัวอักษรที่ป้อนประกอบด้วยสัญลักษณ์พิเศษสองตัวซึ่งทำหน้าที่เป็นเครื่องหมายปลายด้านซ้ายและเครื่องหมายปลายด้านขวาซึ่งหมายถึงการเปลี่ยนไม่เลื่อนไปทางซ้ายของเครื่องหมายปลายด้านซ้ายหรือทางด้านขวาของเครื่องหมายปลายด้านขวาของเทป
หุ่นยนต์ที่มีขอบเขตเชิงเส้นสามารถกำหนดเป็น 8-tuple (Q, X, ∑, q 0 , ML, MR, δ, F) โดยที่ -
Q เป็นชุดของรัฐที่ จำกัด
X คือตัวอักษรเทป
∑ คือตัวอักษรสำหรับป้อนข้อมูล
q0 เป็นสถานะเริ่มต้น
ML คือเครื่องหมายปลายด้านซ้าย
MRคือเครื่องหมายปลายด้านขวาโดยที่ M R ≠ M L
δ เป็นฟังก์ชันการเปลี่ยนที่จับคู่แต่ละคู่ (สถานะสัญลักษณ์เทป) กับ (สถานะสัญลักษณ์เทปค่าคงที่ 'c') โดยที่ c สามารถเป็น 0 หรือ +1 หรือ -1
F คือชุดของสถานะสุดท้าย
หุ่นยนต์ที่กำหนดขอบเขตเชิงเส้นอยู่เสมอ context-sensitive และหุ่นยนต์ที่มีขอบเขตเชิงเส้นพร้อมภาษาว่างคือ undecidable..