Mesin Turing (Turing Machine)

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

Alan Turing - Penemu Mesin Turing

Push Down Automata (PDA)

Pengertian Push Down Automata

PDA adalah mesin otomata yang memiliki kendali masukan menggunakan teknik LIFO (Last In First Out), untuk menentukan apakah suatu output diterima atau tidak oleh mesin tsb. Dalam melakukan proses peneerimaan input, PDA menggunakan memory stack.

Teori Bahasa dan Automata

Teori Bahasa

Teori bahasa membicarakan bahasa formal (formal languange) , terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor) . Bahasa formal adalah kumpulan kalimat . Semua kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama . Sebuah bahasa formal bisa dibangkitkan oleh dua atau lebih tata bahasa yang berbeda . Dikatakan bahasa formal karena grammar diciptakan mendahului pembangkitan setiap kalimatnya . Bahasa manusia bersifat sebaliknya . grammar diciptakan untuk meresmikan kata-kata yang hidup di masyarakat . Dalam pembicaraan selanjutnya , bahasa formal akan disebut bahasa saja.