Otomata dan pengantar kompilasi

Teori otomata mempelajari tentang mekanisme komputer abstrak atau mesin abstrak. Jauh sebelum ada komputer, tahun 1930, Alan Turing mempelajari mesin abstrak yang punya kemampuan seperti komputer sekarang, dikenal dengan nama Mesin Turing. Tujuan Turing adalah menggambarkan secara jelas apa yang dapat dan yang tidak dapat dilakukan mesin komputing. Kemudian pada tahun 1940 an dan 1950-an, ditemukan mesin abstrak yang lebih sederhana, yaitu “finite automata”. Automata ini, asalnya diperuntukkan untuk membentuk fungsi kecerdasan, berubah secara drastis untuk keperluan lain yang sangat beragam. Tahun 1950-an juga Chomsky mempelajari tentang “tata bahasa” formal, yang sangat berguna untuk pengembangan compiler.

Otomata, berkaitan dengan teori mesin abstrak, yaitu mesin sekuensial yang menerima input, dan mengeluarkan output, dalam bentuk diskrit.

Contoh :Mesin Jaja / vending machine,Kunci kombinasi, Parser/compiler, dll.

Teori bahasa formal, membahas mengenai pembentukan bahasa dengan suatu aturan tatabahasa.Teori Otomata dan bahasa formal, berkaitan dalam hal :

Pembangkitan kalimat/generation : menghasilkan semua kalimat dalam bahasa L berdasarkan aturan yang dimilikinya

Pengenalan kalimat / recognition : menentukan suatu string (kalimat) termasuk sebagai salah satu anggota bahasa L

Kompilasi ; Proses penterjemahan program dari suatu bahasa sumber (source language) menjadi bahasa sasaran (target language).

Teori dasar, tatabahasa dan kelas bahasa

Suatu kalimat dibentuk dengan menerapkan serangkaian aturan produksi pada sebuah simbol ‘akar’. Proses penerapan aturan produksi dapat digambarkan sebagai suatu diagram pohon.

Proses kompilasi dan bahasa formal

[+] Jenisnya menurut tingkat ketergantungan mesin
>Bahasa mesin

>Bahasa Assembly

>Bahasa tingkat tinggi

>Bahasa problem oriented

[+] Keuntungan bahasa tingkat tinggi

>Mudah dipelajari

>Lebih dekat pada permasalahan

>Tidak perlu harus tahu representasi internal

>Lebih mudah didebug

>Tidak bergantung pada mesin

>Dokumentasi yang baik.

Referensi:http://materikuliah-gratis.blogspot.com/2011/08/otomata-dan-pengantar-kompilasi-edisi.html

Konsep Bahasa

Simbol. Simbol merupakan elemen unik terkecil dari bahasa. Dalam sebuah bahasa terdapat sejumlah berhingga simbol-simbol.

Abjad / Alfabet. Merupakan himpunan dari simbol-simbol yang digunakan dalam suatu bahasa. Biasanya dinotasikan dengan S. Misalkan S = {0,1}.

String / word / kata / untai. Adalah barisan berhingga dari simbol-simbol dalam suatu alfabet. Misalkan : S = {0,1} maka 01, 00, 111 merupakan string yang dibentuk berdasarkan alfabet S. Dalam pembahasan, seringkali suatu untai/string dinyatakan dengan suatu variabel, yang biasanya berupa huruf kecil. Contoh : w = “01”; x = “aba”, dst.

Panjang String. Suatu string disusun dari sejumlah n simbol, dengan n³0. Banyaknya simbol yang menyusun sebuah string disebut panjang string, yang disimbolkan dengan |x|. contoh : x = aba , maka |x| = 3.

Untai hampa. Sebuah string dengan panjang nol (n=0) disebut untai hampa dan dinotasikan dengan l. Untai hampa (l) merupakan untai yang dibentuk berdasarkan abjad apa saja. Sehingga l merupakan himpunan bagian dari sembarang himpunan.

Bahasa. Bahasa merupakan himpunan string/kata dari alfabet bahasa itu. Misal untuk

- S₁ = {0,1} maka L1 = {00,01,11,111} merupakan bahasa yang dibentuk berdasarkan abjad S₁ .

- S₂ = {a,b} maka L2 = {a, ab, aab, aaab, … } merupakan bahasa berdasarkan abjad S₂

Misalkan S suatu abjad dan w adalah untai yang dibentuk berdasarkan abjad S. Jika terdapat L yang merupakan bahasa berdasar abjad S dan jika w ada di dalam L, kita tuliskan w Î L, yang berarti w elemen dari L.

Bahasa kosong. Merupakan bahasa yang tidak terdiri dari untai apapun. Dinotasikan dengan {} atau Æ.

Bahasa Universal. Adalah bahasa yang terdiri dari semua kata yang dapat dibentuk berdasarkan suatu abjad S. Misalkan S = {1} maka bahasa universal, dinotasikan S*, adalah S* = {l, 1, 11, 111, 1111, …}

untuk lebih jelasnya bisa visit link Referensi :http://situz-go.blogspot.com/2011/04/teori-bahasa-dan-otomata.html