Pemanfaatan Otomata dan Teori Bahasa

Pemanfaatan Otomata dan Teori bahasa tidak hanya untuk komputer saja tetapi penerapan teori ini sangatlah luas. Finite automata pertama kali dikemukakan ilmuwan yang mempelajari neuron nets dan switching theory. Dengan demikian otomata ini dapat diterapkan pada bidang neuron nets dan switching. Klarifikasi grammar dan context free grammar pertama kali dikemukkan ahli bahasa sebagai sarana mendeskripskikan bahasa manusia. Dengan demikian, otomata juga sangat berguna untuk disiplin bidang linguistik.

Perkembangan-perkembangan selanjutnya adalah para ahli komputer mempelajari dan mengembangkan teori otomata dan teori bahasa formal untuk kepentingan penggunaan sarana komputer yang ampuh sebagai media percobaannya. Teori otomata jelas sangat berguna untuk pengembangan komputer lebih lanjut.

Pemanfaatan otomata dapat diterapkan di beragam bidang yang merupakan asal dari teori otomata ditambah dengan penggunaan di bidang Komputer. Saat ini manusia telah menciptakan ribuan bahasa pemrograman komputer, ribuan bahasa pemrograman belum ditambah bahasa komputer lain seperti bahasa markup, bahasa typesetting, bahasa perintah, bahasa query, bahasa printer, bahasa pengenalan pola seperti pada penerapan penjaminan kualitas sirkuit elektronik yang menggunakan ekspresi regular untuk menyatakan pola sirkuit elektronik. 

Seluruh bidang aplikasi yang menyatakan persoalan sebagai serangkaian state yang senantiasa harus ditelusuri saat hidup aplikasi dan/atau untuk menemukan solusi adalah peluang untuk penerapan otomata.

Seluruh bidang aplikasi yang berkehendak menyatakan keteratuaran sesuatu (struktur) atau kejadian atau rentetan kejadian yang mengikuti suatu kumpulan aturan tertentu dalam pembentkan barisan sesuatu yang berhingga atau tidak berhingga merupakan peluang penerapan teori otomata dadn teori bahasa formal.

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.