Linear Bounded Automata

Linear Bounded Automata adalah mesin Turing non-deterministik multi-track berisi beberapa pita dengan panjang terbatas. Linear bounded automata memiliki kemiripan dengan mesin Turing dimana sama-sama menggunakan tape, tetapi pada mesin ini adalah finite yakni terbatas.

Linear bounded automata (LBA) adalah mesin yang berdasar pada state,sebuah tape yang berisi input string, dan sebuah read/write head yang bergerak ke kiri dan ke kanan di sekitar tape. Mesin ini membandingkan state saat ini dan simbol pada tape pada posisi head dengan jumlah aturan yang terbatas untuk menentukan state berikutnya,simbol mana yang akan ditulis pada tape, dan ke arah mana head akan bergerak.

Tata bahasa tipe ini dapat direpresentasikan oleh mesin otomata :

Aaac -> bBcd

aaCD -> ddCCA

Linear bounded automata (LBA), pada dasarnya, adalah mesin Turing yang komputasinya dibatasi pada jumlah pita tempat input ditulis. Kita dapat membayangkannya sebagai seperangkat keadaan terbatas, alfabet terbatas (termasuk penanda akhir kanan dan kiri khusus [dan]), keadaan awal yang ditentukan, dan sekumpulan instruksi terbatas dalam bentuk yang sama dengan quadruple untuk Mesin Turing. Kita berasumsi, bagaimanapun, bahwa input ke LBA diberikan antara endmarker yang ditunjuk, yaitu sebagai [w], dan bahwa LBA tidak memiliki instruksi yang memungkinkannya untuk bergerak melewati endmarker ini atau untuk menghapus atau menggantinya. Dengan demikian, kepala pita hanya dapat bergerak di bagian pita yang pada awalnya ditempati oleh w, meskipun suatu formulasi setara LBA menetapkan batas pada pita yang dapat digunakan tidak sama dengan panjang input tetapi lebih sebagai fungsi linier dari panjang input. (Fungsi linier dalam variabel x adalah dari bentuk ax + b, di mana a dan b adalah konstanta. Nilai ax + b untuk setiap nilai x pada kertas grafik memberikan garis lurus, sedangkan fungsi plot  yang melibatkan x2, x3 , dll. memberikan kurva.) Ini adalah sumber nama untuk automata ini  ruang komputasi yang diizinkan dibatasi oleh fungsi linear dari panjang string input.

Panjang = fungsi (Panjang string input awal, konstan c)

Informasi memori ≤ c × Informasi input

Perhitungan dibatasi oleh area yang terikat konstan. Alfabet input berisi dua simbol khusus yang berfungsi sebagai penanda ujung kiri dan penanda ujung kanan, yang berarti transisi tidak bergerak ke kiri dari penanda ujung kiri atau ke kanan penanda ujung kanan pita.

Otomata yang dibatasi linier dapat didefinisikan sebagai 8-tupel (Q, X, ∑, q0, ML, MR, δ, F) di mana,

Q    : Adalah seperangkat status terbatas
X    : Adalah alfabet rekaman
∑    : Adalah alfabet input
q0   : Adalah kondisi awal
ML : Adalah penanda ujung kiri
MR : Adalah penanda ujung kanan di mana MR ≠ ML
δ     : Adalah fungsi transisi yang memetakan setiap pasangan (Status, simbol pita) ke (Status, simbol           pita, Konstan 'c') di mana c dapat berupa 0 atau +1 atau -1
F     : Adalah himpunan status akhir.

Linear Bounded Automata deterministik selalu peka terhadap konteks (context-sensitive) dan Linear Bounded Automata dengan bahasa kosong tidak akan bisa memutuskan.

Akhir Penanda Kiri                                                   Akhir Penanda Kanan

Suatu bahasa disebut bisa memutuskan atau Rekursif (fungsi yang memanggil dirinya sendiri secara langsung ataupun tidak) jika ada mesin Turing yang menerima dan berhenti pada setiap string input w. Setiap bahasa yang dapat memutuskan dinamakan Turing-Acceptable.

Keputusan dari suatu masalah (P) dapat diputuskan jika bahasa (L) dari semua instance ya ke P dapat ditentukan.
Untuk bahasa yang dapat menentukan, untuk setiap string input, TM berhenti pada status accept atau reject seperti yang digambarkan dalam diagram berikut

Contoh 1

Cari tahu apakah masalah berikut ini dapat ditentukan atau tidak :
Apakah angka 'm' prima?

Jawaban

Bilangan prima = {2, 3, 5, 7, 11, 13, ………… ..}
Bagi angka ‘m’ dengan semua angka antara ‘2’ dan ‘√m’ mulai dari ‘2’.
Jika salah satu dari angka-angka ini menghasilkan sisa nol, maka ia pergi ke "Rejected", jika tidak pergi ke "Accepted". Jadi, di sini jawabannya bisa dibuat dengan 'Ya' atau 'Tidak'.

Oleh karena itu, ini adalah masalah yang dapat diputuskan.

Sumber :
https://link.springer.com/chapter/10.1007/978-94-009-2213-6_20
https://prezi.com/drtqfxnwusl3/linear-bounded-automata/
https://www.tutorialspoint.com/automata_theory/linear_bounded_automata.htm