Uncategorized

MESIN TURING

* Mesin Turing

•Pada PDA (Push Down Otomata) digunakan stack untuk menyimpan dan mengakses data inputan. Tetapi hal ini menyebabkan kemampuan kerja PDA yang terbatas karena pada prinsip stack,hanya data teratas yang bisa diakses. Ini menyebabkan keterbatasan PDA.

•Mesin turing menggunakan pita (tape) sebagai memori yang berbentuk array . Hal ini menyebabkan data pada pita dapat diakses dari mana saja.*Spesifikasi Mesin Turing
1.Mesin turing memiliki pita berupa array sebagai memori yang dapat menyimpan sebuah simbol tunggal2.Mesin turing memiliki head sebagai penunjuk posisi yang sedang diakses pada pita3.Head dapat bergerak kekanan/kekiri pada pita sesuai fungsi transisi yang ditetapkan untuk membaca inputan4.Head juga  dapat melakukan penulisan/ mengubah isi pita
*Sebuah mesin turing secara formal dinyatakan dalam 7 tupel,M = (Q, S, G, d, S, F, b)Dimana:Q =  himpunan state S = himpunan simbol input G = simbol pada pita,termasuk blank d = fungsi transisi S = state awal (S anggota elemen Q) F = himpunan state akhir b = simbol kosong (menandakan bagian yang tidak terisi)
*Pembacaan fungsi transisi pada mesin turingMisal : d (q1,a) = (q1,b,R) dibaca :Pada state q1 yang menunjukkan karakter a pada pita, maka karakter pada state tersebut berubah menjadi b dan head bergerak ke kanan dengan menunjuk array sebagai  state q1
*Prinsip Kerja mesin Turing1.Lihat state semula dan simbol yang ditunjuk head2.Berdasarkan fungsi transisinya,tentukan:-state berikutnya-Lakukan penulisan ke pita-Gerakkan head ke kanan dan ke kiri3.Bila dari pasangan state dan simbol yang ditunjuk head tidak ada lagi fungsi transisinya,berarti mesin turing berhenti4.Bila mesin turing berhenti di dalam state final (F) , berarti input diterima. Sebaliknya jika mesin berhenti tidak pada state akhir,maka berarti inputan tersebut ditolak.

Web Refrensi : https://www.budiluhur.ac.id/

Leave a Reply

Your email address will not be published. Required fields are marked *