April 18, 2012

Teori Bahasa & Otomata

Setelah menghadapi ujian makul ini ada baiknya saya poskan materinya. sumber materi dari dosen kampus saya amikom yogyakarta tujuan saya mempostingkan materi ini adalah agar dapat saya buka sewaktu-waktu saya butuhkan dimanapun saya berada selama masih ada jaringa internet. selain itu juga agar bisa berbagi informasi dengan teman-teman pengguna internet lainnya:


Pengertian


Komputer mengikuti sejumlah prosedur sistematis, atau algoritme, yang dapat diaplikasikan untuk serangkaian input (string) yang menyatakan integer dan menghasilkan jawaban setelah sejumlah berhingga langkah. Teori otomata adalah
studi tentang peralatan atau “mesin” komputasi abstrak, yang dapat didefinisikan
secara matematis. Tahun 1930-an Alan Turing telah mempelajari mesin abstrak yang memiliki kemampuan seperti komputer sekarang (dalam hal apa yang dihitung). Mesin abstrak merupakan model teoritis dari perangkat keras atau perangkat lunak yang digunakan dalam teori otomata.
Tipe paling sederhana dari mesin abstrak adalah finite automaton atau finite state machine. Prinsip yang mendasari mesin ini adalah sistem pada setiap saat dalam salah satu dari sejumlah state berhingga dan bergerak diantara state-state tersebut dalam merespon sinyal input individual.

Model Komputasi
Teori otomata mempelajari model mesin komputer menggunakan model matematika. Namun matematika yang digunakan benar-benar berbeda dibanding matematika klasik dan kalkulus. Model yang digunakan adalah model mesin state atau model transisi state.
Terdapat tiga topik utama di teori otomata yaitu:
1.      Finite automata (FA) atau disebut Finite State Automata (FSA). FSA terbagi menjadi Deterministic Finite Automata (DFA) dan Non-Derministik Finite Automata (NDFA).
2.      PushDown Automata (PDA) terbagi Deterministic Pushdown Automata (DPDA atau DPA) dan NonDertministik Automata(NDPA)
3.      Turing Machine

Peran Teori Bahasa dan Otomata pada Ilmu Komputer
Ilmu komputer memiliki dua komponen utama : pertama, model dan gagasan mendasar mengenai komputasi, kedua, teknik rekayasa untuk perancangan sistem komputasi, meliputi perangkat keras dan perangkat lunak, khususnya penerapan rancangan dari teori. Teori Bahasa dan Otomata merupakan bagian pertama. Secara teoritis ilmu komputer diawali dari sejumlah berbeda disiplin ilmu: ahli biologi mempelajari neural network, insinyur elektro mengembangkan switching sebagai tool untuk mendesain hardware, matematikawan bekerja mendasarkan logika, dan ahli bahasa menyelidiki tata bahasa untuk natural language.

Finite State Automata dan ekspresi reguler awalnya dikembangkan berdasarkan pemikiran neural network dan switching circuit. Finite State Automata merupakan tool yang sangat berguna dalam perancangan lexical analyzer, yaitu bagian dari kompilator yang mengelompokkan karakter-karakter dalam ke dalam token, yang berupa unit terkecil seperti nama, variabel dan keyword. Dalam sistem penulisan kompilator secara otomatis akan mentransformasikan ekspresi regular ke dalam finite state automata  dan ekspresi regular dipakai pula dalam text editor, pattern matching, sejumlah pemrosesan teks, dan program file-searching, dan sebagai konsep matematis untuk aplikasi di disiplin lain seperti logika.

Finite automata terdiri dari sejumlah berhingga state. Dalam banyak sistem
dan komponen seperti dijelaskan di atas, sejumlah berhingga state digunakan untuk mengingat bagian dari histori sistem. Karena hanya terdapat sejumlah berhingga state, secara umum histori sistem secara keseluruhan tidak dapat disimpan/diingat, sehingga sistem harus dirancang untuk mengingat apa yang penting dan melupakan apa yang tidak penting.
Context free grammer dan pushdown automata digunakan dalam spesifikasi bahasa komputer (pemrograman, markup, kamus data, query, perintah, script, printer). Dalam parser, bagian kompilator yang memriksa kebenaran sintaks program. Pemahaman pushdown automata sangat menyederhanakan proses parsing. Proses parsing yang berlangsung sangat cepat adalah berkat pemahaman mendalam teknik parsing bebasis pada pengetahuan mengenai context free grammer.
Mesin Turing merupakan pemodelan mesin komputasi yang ampuh. Berdarkan mesin Turing dapat diidentifikasi ketidakmungkinan penulisan program. Bila dinyatakan tidak dapat dikomputasi mesin Turing berarti persoalan tidak mungkin dapat diselesaikan secara komputasi dengan mesin komputasi apapun. Namun bila dikatakan persoalan dapat dikomputasi mesin Turing bukan berarti 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 dikomputasi.


◄ Posting Baru Posting Lama ►
 

Total Pageviews

Copyright © 2012. InfoneRoy - All Rights Reserved B-Seo Versi 5 by Bamz thanks to Asmawi