Linier Bounded Automata adalah mesin Turing non-deterministik multi-track dengan pita beberapa panjang terbatas terbatas.
Length = function (Length of the initial input string, constant c)
Sini,
Memory information ≤ c × Input information
Perhitungan dibatasi pada area yang dibatasi 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 rekaman.
Otomat terikat linier dapat didefinisikan sebagai 8-tupel (Q, X,,, q 0 , ML, MR, δ, F) di mana -
- Q adalah seperangkat status terbatas
- X adalah alfabet rekaman
- ∑ adalah alfabet input
- q 0 adalah kondisi awal
- M L adalah penanda ujung kiri
- M R 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
Otomat terikat linear deterministik selalu peka konteks dan otomat terikat linier dengan bahasa kosong tidak dapat ditentukan . .
POWER OF LBA
LBA lebih kuat dari PDA misalnya: a n b n c n | n ≥1
tidak dapat diterima oleh PDA sedangkan itu dapat diterima oleh LBA tanpa menggunakan spasi tambahan atau simbol BLANK.
Pendekatan
Misalkan input adalah: "aaabbbccc"
Tandai 'a' sebagai 'X' dan bergerak ke kanan, tandai 'b' sebagai 'X' dan bergerak ke kanan, tandai 'c' sebagai 'X' dan bergerak ke kiri. Dan ulangi proses ini sampai semua simbol ditandai sama
Pendekatan
Misalkan input adalah: "aaabbbccc"
Tandai 'a' sebagai 'X' dan bergerak ke kanan, tandai 'b' sebagai 'X' dan bergerak ke kanan, tandai 'c' sebagai 'X' dan bergerak ke kiri. Dan ulangi proses ini sampai semua simbol ditandai sama
Contoh Standard LBA :
Berikut ini adalah contoh standar dari LBA yang perlu diingat
- L = {a n b n c n | n ≥1}
- L = {a n! | n ≥ 0}
- L = {a n | n = m 2 , m ≥ 1}, berarti n adalah kuadrat sempurna
- L = {a n | n adalah prima}
- L = {a n | n bukan bilangan prima}
- L = {ww | w ε {a, b} + }
- L = {w n | w ε {a, b} + , n ≥ 1}
- L = {www R | w ε {a, b} + }
Daftar Pustaka :
Tambahkan Komentar