Otomata dan Bahasa Formal

1. Otomata hingga
Otomata hingga melibatkan stata dan transisi antar stata yang merupakan tanggapan atas masukan. Otomata hingga berguna untuk merekayasa perangkat lunak-perangkat lunak tertentu termasuk komponen lexical analyzer yang terdapat pada compiler dan sistem pemeriksa kebenaran pada sirkuit atau protocol.
Automata merupakan suatu studi abstrak yang terdiri dari suatu himpunan tiga tupel yaitu M={S, S, D} dimana S menyatakan state (keadaan); S menyatakan input; dan D menyatakan penentuan keadaan nilai.
Subjek utama dalam tulisan ini adalah mesin sekuensial, sebuah struktur penting yang menjadi dasar dari pirantipiranti, aktivitas, dan proses pengambilan keputusan, terutama yang berhubungan dengan komputer.
Automata merupakan suatu sub struktur utama dari mesin atau proses sekuensial tersebut. Pada mesin sekuensial, suatu proses dibangkitkan oleh masukan tertentu dan menghasilkan keluaran tertentu pula berdasarkan informasi yang dimiliki.
Automata merupakan struktur transisi dari suatu mesin sekuensial, dengan demikian pada dasarnya automata adalah bagian dari suatu mesin sekuensial dengan struktur keluaran yang telah dihapus.
Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu Pemodelan geografis berbasiskan Cellular Automata (CA) dan Multi Agent System (MAS) memiliki kekurangan:

• Pada Cellular Automata, automata secara individual dapat menyebarkan informasi, tapi tidak bebas bergerak
• Pada Multi Agent System, automata bergerak secara bebas dan mandiri, tetapi mengabaikan sifat-sifat ruang (space) dan keruangan (spasial).
Cellular Automata
Automata merupakan bentuk jamak dari automaton. Automaton adalah suatu mekanisme pemrosesan secara diskrit, berdasarkan keadaan internal dari suatu obyek. Dalam automata, obyek (sel atau agent) memiliki keadaan dan aturan yang menentukan perubahan.
Berikut sifat-sifat dari Automaton:
• Berganti keadaan menurut waktu
• Sesuai seperangkat aturan
• Berdasarkan keadaan internal dan eksternal
• Dalam langkah yang berurutan.
1.2 .Ekspresi Reguler
Exspresi regular merupakan notasi structural untuk mendeskripsikan pola-pola yang sama dan dapat diwakili oleh otomata hingga. Exspresi regular digunakan pada berbagai tipe perangkat lunak yang biasa kita gunakan, termasuk perangkat lunak untuk mencari pola-pola dalam texs atau nama file.
1.3. Tata Bahasa Bebas-Konteks
Tata bahasa bebas konteks ini merupakan notasi penting yang digunakan untuk mendeskripsikan sruktur bahasa pemograman dan himpunan-himpunan untai yang berhubungan; digunakan untuk membuat komponen parser pada compiler.
1.4. Mesin Turing
Mesin turing adalah otomata yang menjadi model computer yang kita kenal saat ini. Mesin turing memungkinkan kita untuk mempelajari decidability, yaitu pertanyaan mengenai apa yang dapat dan tidak dapat dikerjakan oleh computer. mesin ini juga memungkinkan kita menbedakan tractable problem (dapat dipecahkan dalam waktu polynomial) dari intractable problem (tidak dapat dipecahkan dalam waktu polynomial).
1.5. Pembuktian Deduktif
Metode pembuktian yang mendasar ini dilakukan dengan cara mendaftar stateman yang diketahui benar atau yang secara logika mengikuti beberapa statemen sebelumnya.
1.6. Pembuktian stetemen jika-maka
Banyak teorema memiliki bentuk “jika (sesuatu) maka (sesuatu yang lain)”. Stateman tersebut atau stateman yang mengikuti “jika” merupakan hipotesis dan yang mengikuti “maka” adalah kesimpulan. Pembuktian deduktif statemen jika-maka dimulai dengan hipotesis dan dilanjutkan dengan statemen yang mengikuti secara logika hipotesis dan statemen sebelumnya, hingga kesimpulan dibuktikan sebagai salah satu statemen.
1.7. Pembuktian stateman jika dan hanya jika
Ada teorima-teorema yang memiliki bentuk “(sesuatu) jika dan hanya jika (sesuatu yang lain)”. Statemen-statemen tersebut dibuktikan dengan cara statemen “jika-maka” pada kedua arah. Jenis teorema yang sama mengklain kasamaan himpunan-himpunan yang dideskripsikan dengan dua cara yang berbeda;
1.8. Pembuktian Kontrapositif
Pembuktian kontrapositif kadang kala,  lebih mudah untuk membuktikan statemen “jika H maka C” dengan membuktikan “jika hal dan bukan C maka (sesuatu yang diketahui salah).” Pembuktian dengan cara ini disebut sebagai pembuktian dengan kontradiksi.
1.9. Counter example:
Tidak jarang kita diminta untuk menunjukan bahwa suatu statemen tertentu tidak benar. jika statemen memiliki satu atau lebih para meter, makakita dapat menunjukan bahwa statemen tersebut salah sebagai suatu generalisasi dengan menyediakan satu saja counterexample, yaitu suatu penetapan/penyerahan nilai kepada parameter yang membuat statemen tersebut salah.
1.10. Pembuktuan Induktif
Statemen yang memiliki parameter bilangan bulat n sering kali dapat dibuktikan dengan induksi pada n. kita membuktikan statemen tersebut benar atau basis, yaitu sejumblah berhingga kasus untuk nilai n tertentu dan kemudian membuktikan langkah induktif: bahwa jika statemen bernilai benar untuk nilai-nilai hingga n, maka ia juga bernilai benar untuk n + 1.
1.11. Intruksi Struktural
Pada beberapa situasi, teorema yang akan dibuktika secara induktif teorema mengenai suatu kontruksi yang didefinisikan secara rekursif , misalnya pohon (tree). Kita dapat membuktikan teorema mengenai obyek-obyek yang dikontruksi melalui induksi pada jumblah langkah yang digunakan untuk mengkontruksinya. Jenis intruksi ini dirujuk sebagai structural.
1.12. Alfabet
Alphabet adalah sembarang himpunan simbul-simbul.
1.13. Untai (string):
Untai adalah deretan simbul-simbul yang panjangnya berhingga.
1.14. Bahasa Dan Problema
Bahasa adalah himpunan (bisa jadi himpunan tak hingga) untai-untai, seluruhnya memilih timbulnya dari satu alphabet yang sama. Ketika suatu untai bahasa ditafsirkan denggan suatu cara pertanyaan mengenai apakah untai tersebut berada dibahasanya sering disebut sebagai problema.
Bahasa suatu Automata
Otomaton menerima untai-untai. Suatu untai diterima jika sejak dari stata mula, alihan yang disebabkan oleh pemrosesan sombol-simbol untai-untai tersebut. diagram alihan, untai diterima jika terdapat label lintasan dari stata mula kesuatu stata penerima.
• Kontruksi himpunan bagian
Dengan memperlakukan himpunan stata NFA sebagai stata suatu DFA, kita dapat mengkonfersi sembarang NFA menjadi DFA penerima bahasa yang sama.
Teori Bahasa Automata Dalam Ilmu Komputer
Suatu teori hanya menarik jika dapat membantu dalam mencari solusi terbaik. Tanpa penerapan timbul pertanyaan, mengapa mempelajari teori?
Teori memberikan konsep dan prinsip yang menolong untuk memahami perilaku dari suatu persoalan yang berkorelasi dengan teori tersebut. Bidang ilmu komputer meliputi topik yang luas, dari perancangan mesin sampai pemrograman. Disamping perbedaan yang ada, terdapat keseragaman prinsip-prinsip umum yang dipakai. Untuk mempelajari prinsip-prinsip dasar tersebut, kita mengkonstruksi suatu mesin otomata sebagai model abstrak dari komputer dan komputasi.

Teori bahasa membicarakan bahasa formal (formal language), yang terdiri dari kumpulan kalimat. Sebuah kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama oleh dua atau lebih tata bahasa yang berbeda terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor).

Bahasa dalam hal ini berisi semua string yang dapat dihasilkan menggunakan aturan-aturan grammar yang mempunyai nilai/ manfaat sangat besar di ilmu informatika/ computer karena untuk mendeskripsikan dan mendefinisikan sintaks bahasa pemrograman dan bahasa-bahasa formal lain dan dapat diterapkan pada perancangan kompilator.

Teori otomata merupakan kajian mengenai perangkat komputasi abstrak atau bisa dikatakan mesin abstrak. Teori menyediakan konsep-konsep dan prinsip-prinsip yang dapat membantu kita memahami sifat umum suatu bidang kajian yang berkaitan dengan Automata.

Sedangkan otomata (Automata) adalah suatu sistem yang terdiri atas sejumlah berhingga state yang mempelajari tentang mesin abstrak yang menerima input dan mengeluarkan output dalam bentuk diskret (satu per satu). Dimana state adalah suatu kondisi yang menyatakan informasi mengenai input yang lalu sedangkan input pada otomata dianggap sebagai batas yang harus dikenali oleh mesin.
29 Juli 2009 17.50

Anonim mengatakan...
Nama : Indra Ade Mula Putra
NIM : 20094260


Teori otomata yang selama ini banyak diterapkan dalam bidang tata bahasa formal khususnya dalam sebuah pengembangan compiler, juga dapat digunakan untuk melakukan pemodelan atau pendekatan pemecahan masalah - masalah yang berkaitan dengan aplikasi didalam bidang kecerdasan buatan.