Linear Bounded Automata

Linear Bounded Automata

Linear bounded automata (LBA) adalah mesin yang berdasar pada state, sebuah tape yang berisi input strung, dan sebuah read/write head yang bergerak ke kiri dan ke kanan disekitar tape. Mesin ini membandingkan state saat ini dan simbol dari 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.

Linear bounded automata memiliki kemiripan dengan mesin turing dimana sama-sama menggunakan tape, tetapi pada mesin ini adalah finite yakni terbatas.

Length = function (Length of the initial input string, constant c)

Perhitungan dibatasi pada area yang dibatasi konstan. Alfabet input berisi dua simbol khusus yang berfungsi sebagai tanda ujung kiri dan tanda ujung kanan yang berarti transisi tidak bergerak ke kiri dari penanda ujung kiri atau ke kanan penanda ujung kanan pada tape tersebut.

Linear bounded automata terdiri dari 8 tuples:

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 M R ≠ M L

δ adalah fungsi transisi yang memetakan setiap pasangan (negara, simbol pita) ke (negara, simbol pita, Konstan 'c') di mana c dapat berupa 0 atau +1 atau -1

F adalah himpunan status akhir

Linear bounded automata deterministik selalu context-sensitive dan linear bounded automata dengan bahasa kosong tidak dapat ditentukan.

Daftar Pustaka

Pratama, Rizky. 2016. Linear Bounded Automata. diakses dari https://prezi.com/drtqfxnwusl3/linear-bounded-automata/, pada 6 Maret 2020.
Tutorialspoint.com. 2020. Linear Bounded Automata. diakses dari https://www.tutorialspoint.com/automata_theory/linear_bounded_automata.htm, pada 6 Maret 2020.