Linier Bounded Automata

       Automata terikat linier (Liner Boinded Automata), adalah mesin Turing non-deterministik multi-track dengan pita beberapa panjang terbatas terbatas.

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

Sini,

Informasi memori ≤ c × Informasi input

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 yang dibatasi linear 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 .

referensi :

https://www.tutorialspoint.com/automata_theory/linear_bounded_automata.htm

Mesin Turing

Pengertian Mesin Turing

Mesin Turing adalah sebuah automata yang memiliki kemampuan lebih tinggi dari pada FSA (Finite State Automata) dan PDA (Push Down Automata) yang bisa menerima bahasa-bahasa reguler, bahasa konteks dan bahasa lainnya, dari segi aksi dan komponennya.

Sejarah Mesin Turing

Mesin Turing ini diusulkan pada tahun 1936 oleh Alan Turing, seorang matematikawan Inggris sebagai model matematis sederhana sebuah komputer.

Meskipun sederhana, Mesin Turing memiliki kemampuan untuk menggambarkan perilaku komputer general-purpose.

Mesin Turing dapat digunakan untuk menghitung kelas fungsi bilangan bulat yang dikenal sebagai fungsi rekursif sebagian (partial recursive function).

Sama seperti Finite State Automata dan Push Down Automata yang dapat mengenali bahasa formal, maka mesin Turing juga dapat berperan sebagai mesin pengenal bahasa formal.

Bahasa yang dikenali oleh Mesin Turing adalah bahasa tanpa-pembatasan (non-restricted language), yang disebut juga himpunan terenumerasi rekursif (recursively enumerable set).

Model Mesin Turing

Sebuah mesin Turing terdiri dari komponen-komponen :

1. Pengendali berhingga (finite control)
2. Pita masukan dengan sifat :

• Panjangnya tidak berhingga (ujung kiri terbatas, ujung kanan tidak terbatas)

• Dapat dibaca maupun ditulis

• Sel yang tidak berisi simbol masukan akan berisi simbol kosong (blank = B)

PERBEDAAN MESIN TURING DENGAN FSA DAN PDA

Penjelasan

Mesin Turing mengenal gerakan ke kanan (Right) dengan symbol R dan ke kiri (Left) dengan simbol L.

Mesin terdiri dari :

• Q : Himpunan Stata
• Σ : Himpunan Input
• δ : Stata Awal
• r : Himpunan Simbol Ditransisi
• S : Fungsi Transisi
• B/ѣ : Blank
• F : Stata akhir

Contoh Kasus

Diketahui :

• Q : {𝑞_0, 𝑞_1, 𝑞_2, 𝑞_3, 𝑞_4, 𝑞_5, 𝑞_6}
• Σ : {0,1}
• δ : 𝑞₀
• r : {0,1,B}
• F : 𝑞₆

Apakah bahasa ini diterima atau ditolak mesinkah ?

1. 𝑞₀, 0IB
2. 𝑞₀, 00IB

Pembahasan

1. 𝑞₀, 0IB

• 𝑞₀, 0IB
• 𝑞₁, BIB
• 𝑞₂, BIB
• 𝑞₄, BIB
• 𝑞₄, BBB
• 𝑞₆, 0BB 

Input Diterima

2. 𝑞₀, 00IB

• 𝑞₀, 00IB
• 𝑞₁, 0BIB
• 𝑞₂, 0BIB
• 𝑞₄, 0BIB
• 𝑞₄, 0BBB
• 𝑞₆, 00BB 

Input Diterima

referensi :

fosma-165-riau.id/2017/01/pengertian-sejarah-model-mesin-turing_26.html