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 penyimpan...