Linear Bounded Automata
Linear Bounded Automata (LBA) adalah jenis mesin turing yang memiliki
batasan. Pada tahun 1960, Myhill memperkenalkan LBA yang termotivasi
dari penelitian Rabin dan Scott pada tahun 1959 tentang finite automata.
LBA adalah mesin abstrak yang memiliki kemiripan dengan mesin turing,
hanya saja ketika input diberikan ke dalam proses komputasi, tape tidak diperbolehkan untuk melewati wilayah batas dari infinite tape. Tape itu sendiri memiliki panjang tak terhingga dengan maksud untuk mengakomodasi masukan dari panjang yang bisa diatur semaunya.
Seperti mesin turing, Linear Bounded Automata adalah finite state machine yang dilengkapi dengan tape. Namun tidak seperti mesin turing, sistem LBA hanya memiliki state secara terbatas untuk tiap input; yaitu, untuk tiap inputnya, LBA berlaku sebagai automata terbatas. Perbedaan yang berkaitan antara LBA dan FSA adalah jumlah state pada masing-masing dari keduanya. Jumlah state pada FSA adalah tetap, sedangkan pada LBA jumlah state-nya bervariasi tergantung kepada fungsi linear dari jumlah masukan yang diberikan. Ada beberapa tata bahasa yang dapat dikenali oleh Linear Bounded Automata tetapi tidak oleh Pushdown Automata misalnya bahasa konteks sensitif.
Linear Bounded Automata adalah mesin turing non-deterministic yang memiliki 3 kondisi:
Q = Himpunan State
X = Alfabet Tape
∑ = Himpunan Simbol Input
q0 = State Awal
ML = Left end marker
MR = Right end marker di mana MR ≠ ML
δ = Fungsi Transisi
F = State Akhir
Seperti mesin turing, Linear Bounded Automata adalah finite state machine yang dilengkapi dengan tape. Namun tidak seperti mesin turing, sistem LBA hanya memiliki state secara terbatas untuk tiap input; yaitu, untuk tiap inputnya, LBA berlaku sebagai automata terbatas. Perbedaan yang berkaitan antara LBA dan FSA adalah jumlah state pada masing-masing dari keduanya. Jumlah state pada FSA adalah tetap, sedangkan pada LBA jumlah state-nya bervariasi tergantung kepada fungsi linear dari jumlah masukan yang diberikan. Ada beberapa tata bahasa yang dapat dikenali oleh Linear Bounded Automata tetapi tidak oleh Pushdown Automata misalnya bahasa konteks sensitif.
Linear Bounded Automata adalah mesin turing non-deterministic yang memiliki 3 kondisi:
- Alfabet masukannya mengikutsertakan dua simbol spesial, yaitu left dan right end marker (penanda batas kiri dan kanan)
- Transisinya tidak mencetak simbol lain melebihi end marker
- Transisinya tidak berpindah ke kiri left end marker atau tidak ke kanan right end marker
Q = Himpunan State
X = Alfabet Tape
∑ = Himpunan Simbol Input
q0 = State Awal
ML = Left end marker
MR = Right end marker di mana MR ≠ ML
δ = Fungsi Transisi
F = State Akhir