Teori Bahasa dan Otomata (TBO) – Pendahuluan

Pada materi Teori Bahasa Otomata (TBO) ini dibahas tentang Pengertian TBO, Model Komputasi TBO, Peranan TBO dalam Ilmu Komputer dan Contoh Penerapan TBO.

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 menjadiDeterministic 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,

Teori Bahasa dan Otomata

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.
Contoh Penerapan Teori Bahasa Otomata
Contoh 1:
Model switch on/off digambarkan sebagai berikut :
Model tersebut mengingat apakah switch berada dalam state “on” atau state
“off”. Model memungkinkan user untuk menekan tombol yang memiliki
pengaruh berbeda tergantung pada keadaan switch:
• Jika switch berada dalam state “off” maka setelah tombol ditekan state
berubah menjadi “on”.
• Jika switch berada dalam state “on” maka setelah tombol ditekan state
berubah menjadi “off”.
Model pada Gambar 1 dapat dipandang sebagai model finite automato sederhana.

Download Materi Selengapknya disini: Teori Bahasa dan Otomata (TBO) – Pendahuluan

PENGUMUMAN WEBSITE JAKA
Anda sedang membaca artikel tentang Teori Bahasa dan Otomata (TBO) – Pendahuluan dan anda bisa menemukan artikel Teori Bahasa dan Otomata (TBO) – Pendahuluan ini dengan url https://jakaprimamaulana.blogspot.com/2015/10/pada-materi-teori-bahasa-otomata-tbo.html, anda boleh menyebar luaskannya atau mengcopy paste-nya jika artikel Teori Bahasa dan Otomata (TBO) – Pendahuluan ini sangat bermanfaat bagi teman-teman anda, namun jangan lupa untuk meletakkan link Teori Bahasa dan Otomata (TBO) – Pendahuluan sumbernya. jika artikel ini bagus anda dapat membagikan kepada teman anda

Tweet

Posted by prima