Sejarah Linear Bounded Automata
Pada tahun 1960, John Myhill memperkenalkan model Automata yang sekarang dikenal sebagai deterministik Linear Bounded Automaton. Pada tahun 1963, Peter S. Landweber membuktikan bahwa bahasa yang diterima oleh LBA deterministik peka terhadap konteks. Pada tahun 1964, S.-Y. Kuroda memperkenalkan model automata terbatas linier (nondeterministik) yang lebih umum, mencatat bahwa bukti Landweber juga berfungsi untuk automata terikat linier nondeterministik, dan menunjukkan bahwa bahasa yang diterima oleh mereka adalah bahasa yang peka konteks. |
| John Myhill |
Pengertian
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.
Linear Bounded Automata.
Aaac -> bBcd
aaCD -> ddCCA
Linear bounded automata memiliki kemiripan dengan mesin Turing dimana sama-samamenggunakan 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 Linear Bounded Automata didefinisikan sebagai 9 tuple
M={Q, ∑, Г, δ, q0, B, F, \YLeft, \YRight) .
Q: Himpunan state.
∑: Himpunan simbol input.
Г: Simbol dalam pita.
δ: Fungsi transisi.
q0: State awal.
\YLeft : Left endmarker (kiri).
\YRight: Right endmarker (kanan).
B: Simbol kosong.
F: Himpunan state akhir.
Syarat Linear Bounded Automata
- Simbol pada ruas sebelah kiri harus minimal ada sebuah Variabel.
- Panjang string ruas kiri harus lebih kecil atau sama dengan ruas kanan.
Contoh :
Ab → DeF
CD → eF
Sumber :
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.
Linear Bounded Automata.
Aaac -> bBcd
aaCD -> ddCCA
Linear bounded automata memiliki kemiripan dengan mesin Turing dimana sama-samamenggunakan 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 Linear Bounded Automata didefinisikan sebagai 9 tuple
M={Q, ∑, Г, δ, q0, B, F, \YLeft, \YRight) .
M={Q, ∑, Г, δ, q0, B, F, \YLeft, \YRight) .
Q: Himpunan state.
∑: Himpunan simbol input.
Г: Simbol dalam pita.
δ: Fungsi transisi.
q0: State awal.
\YLeft : Left endmarker (kiri).
\YRight: Right endmarker (kanan).
B: Simbol kosong.
F: Himpunan state akhir.
Syarat Linear Bounded Automata
- Simbol pada ruas sebelah kiri harus minimal ada sebuah Variabel.
- Panjang string ruas kiri harus lebih kecil atau sama dengan ruas kanan.Contoh :
Ab → DeF
CD → eF
Tidak ada komentar:
Posting Komentar