Pengertian Mesin Turing, Linear Bounded, Push Down Automata, Finite State Automata, DFA, dan NFA

Mesin Turing adalah model yang sangat sederhana dari komputer. Secara esensial, mesin Turing adalah sebuah Finite automaton yang miliki sebuah tape tunggal dengan panjang takter hingga yang dapat membaca dan menulis data. Mesin Turing menggunakan notasi seperti ID-ID pada PDA untuk menyatakan konfigurasi dari komputasinya. Stack pada PDA memiliki keterbatasan akses. Elmen yang dapat diakses hanya elemen yang ada pada top stack. Pada Mesin Turing, memori akan berupa suatu tape yang pada dasarnya merupakan array dari sel-sel penyimpanan."isualisasi dari sebuah mesin Turing diberikan oleh gambar berikut :

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.

Push Down Auto (PDA) merupakan perluasan dari non-deterministic finite automata yang merupakan suatu cara untuk mendifinisikan bahasa regular. PDA digambarkan sebagai tempat penyimpanan yang tidak terbatas, yaitu berupa stack/ tumpukan. Stack digunakan untuk menyimpan sejumlah symbol yang diakses dengan aturan LOFI(Last In Firt Out). Stack tersebut dapat dibaca, di-push (pemmasukan elemen), dan di-pop (pengmbilan elemen) hanya pada bagan atas dari stack(top stack).

Finite State Automata Model matematika suatu sistem yang menerima input dan output diskrit Mesin automata dari bahasa Regular Tidak memiliki tempat penyimpanan sehingga kemampuan mengingat terbatas (contoh: elevator/lift) Aplikatif berguna untuk merancang sistem nyata.

Finite Automata dibagi menjadi Deterministic Finite Automata (DFA) dan Non Deterministic Finite Automata (NFA).

Berdasarkan contoh Deterministic Finite Automata (DFA) dan Non Deterministic Finite Automata (NFA) yang ada di atas, terlihat perbedaan antara DFA dan NFA yaitu :

• NFA : transisi state FSA akibat pembacaan sebuah simbol bersifat tertentu.
• DFA : transisi state FSA akibat pembacaan sebuah simbol bersifat tak tentu.

Sumber tertera :

https://www.scribd.com/doc/208290678/MESIN-TURING-DAN-OTOMATA-AUTOMATA

https://prezi.com/drtqfxnwusl3/linear-bounded-automata/

https://www.slideshare.net/dheazafarina/push-down-automata-49164344

https://docplayer.info/36555908-Teori-bahasa-dan-automata-finite-state-automata-non-finite-state-automata.html