Tiga Model Komputasi

Tiga Model Komputasi - Teori otomata membahas tentang model mesin komputer menggunakan modul matematika. Tetapi matematika yang digunakan sangat berbeda dibandingkan dengan matematika klasik dan kalkulus. Model yang digunakan adalah model mesin state (state machine model) atau model transisi state (state transition model). Terdapat tiga topik utama di teori otomata, yaitu

1. Finite automata (FA) atau disebut juga finite state automata (FSA). FSA terbagi menjadi deterministic finite automata (DFA) dan non deterministic automata (NDFA)
2. Pushdown automata (PDA) terbagi deterministic pushdown automata (DPDA atau DPA) dan nondeterministic pushdown automata (NPDA)
3. Turing machine (TM)

Finite automata dan ekspresi regular
Di tangan seorang ahli, finite automata dan ekspresi regular menjadi model yang sangat berguna dalam perancangan lexical analyzer, yaitu bagian kompilator yang bertugas mengelompokkan karakter-karakter menjadi token-token, yaitu unit bahasa terkecil seperti keyword, identifier dan sebagainya, bertindak sebagai kata di bahasa sehari-hari. Sejumlah model pengembangan kompilator dapat membangkitkan program lexical analyzer dari ekspresi regular secara otomatis.

Penggunaan ekspresi regular dan finite automata ditemukan di beragam aplikasi seperti editor teks, pengenalan/pencarian pola, pengolahan teks (seperti pada bahasa AWK dan Perl), pencarian teks beragam file (grep, fgrep, egrep di sistem UNIX pengelolaan pengembagan perangkat lunak menyatakan perbedaan satu file dengan file lain (program diff), dan sebagainya. Pada pengembangan sistem fault tolerant digunakan finite state machine untuk perancangannya, yaitu sistem yang mampu bertahan terhadap kegagalan-kegagalan sampai suatu ambang.

Pushdown automata dan context free grammar
Setelah pencetusan gagasan context free grammar, Chomsky menunjukkan bahan context free ekvialen mesin abstrak pushdown automata. Maksud ekivalen adalah untuk sembarang context free grammar terdapat pushdown automaton yang dapat mengenali bahasa hasil context free grammar itu. Pushdown automata mengolah sembarang string dan menentukan apakah string itu termasuk bahasanya. Kebalikannya juga berlaku yaitu untuk sembarang pushdown automaton maka bahasa yang dikenalinya dapat dibangkitkan dengan satu context free grammar.

Context free grammar dan pushdown automata digunakan dalam spesifikasi bahasa komputer (pemrograman, markup, kamus data, query, perintah, script, printer, dan sebgainya). Dalam parser, bagian kompilator yang memeriksa kebenar sintaks program. Pemahaman pushdown automata sangat menyederhanakan proses parsing. Proses parsing berlangsung sangat cepat adalah berkat pemahaman mendalam teknik parsing berbasis pada pengetahuan context free grammar.

Mesin Turing
Mesin Turing menggunakan pemodelan mesin komputasi yang ampuh. Berdasar mesin Turing dapat diidentifikasi ketidakmungkinan penulisan program. Jika dinyatakan tidak dapat dikomputasi mesin Turing maka persoalan tidak mungkin dapat diselesaikan secara komputasi mesin komputasi apapun. Namun bila dikatakan persoaan dapat dikomputasi mesin Turing bukan berarti dijamin terdapat algoritma penyelesaian efisien. Mesin Turing sangat penting mengidentifikasi ketidakmungkinan komputasi sehingga kita tidak bersusah payah berusaha memperoleh solusi 100% terhadap fungsi yang diidentifikasi tidak mungkin di komputasi.