TEORI BAHASA DAN AUTOMATA

1. Rangkuman Linguistik dan Komputasi

Linguistik adalah ilmu bahasa. Bergantung dari sudut pandang, dan pendekatan seorang peneliti, seorang peneliti, linguistik seringkali digolongkan ke dalam ilmu kognitif, psikologi, dan antropologi. 

Komputasi bisa diartikan sebagai cara untuk menemukan pemecahan masalah dari data input dengan menggunakan suatu algoritma.

sedangkan, Linguistik Komputasi adalah bidang antar disiplin yang mengkaji pemodelan bahasa alami dengan statistika dan berbasis aturan dari sudut pandang komputasi. Komputer dapat dipakai untuk menganalisis bunyi bahasa.

2. Rangkuman Automata beserta Fungsinya

     Automata adalah mesin abstrak yang dapat mengenali (recognizer), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.

     Untuk memodelkan hardware dari komputer diperkenalkan otomata. Otomata adalah fungsi-fungsi dari komputer digital. Menerima input, menghasilkan output, bisa memiliki penyimpanan sementara dan mampu membuat keputusan dalam mentransformasikan input ke output.

     Sebuah bahasa formal adalah suatu abstraksi terdiri dari himpunan simbol-simbol dan aturan-aturan yang mana simbol-simbol tersebut bisa dikombinaasikan ke dalam entitas yang disebut kalimat.

     Meskipun bahasa formal yang dipelajari disini lebih sederhana daripada bahasa lebih sederhana daripada bahasa pemrograman, meraka mempunyai banyak hal yang penting. Kita bisa mempelajari banyak tentang bahasa pemrograman dari bahasa formal.

     Otomata merupakan suatu sistem yang terdiri atas sejumlah berhingga state, dimana state menyatakan informasi mengenai input yan lalu dandapaty dianggap sebagai memory mesin.

     Input pada mesin otomata dianggap sebagai bahasa yang harus dikenali oleh mesin. Selanjutnya, mesin otomata membuat keputusan yang mengindikasikan apakah input itu diterima atau tidak.

Jenis-Jenis Automata :

      1. Otomata Berhingga Deterministik 

Otomata berhingga deterministik (DFA - Deterministic Finite Automata) adalah sebuah otomata yang fungsi transisinya adalah:

2. Otomata Berhingga Non-Deterministik

Otomata berhingga non-deterministik (NFA - Nondeterministic Finite Automata) berbeda dengan DFA dalam hal fungsi transisinya:

${\displaystyle \delta :Q\times \Sigma \rightarrow {\mathcal {P}}(Q)}$             

Fungsi transisi dalam NFA memetakan pasangan ${\displaystyle Q}$ dan ${\displaystyle \Sigma }$ kepada himpunan kuasa dari Fungsi transisi yang didefinisikan seperti ini memungkinkan suatu simbol masukan untuk mengakibatkan transisi dari sebuah state ke beberapa kemungkinan state yang lain.

             3. Otomata Pushdown

Otomata Pushdown adalah salah satu varian otomata dengan 7-tupel   di mana:

•  adalah himpunan berhingga dari state,

•  adalah himpunan simbol-simbol,

•  adalah simbol awal

•  adalah state akhir

•  adalah himpunan berhingga simbol-simbol stack,

• adalah simbol awal stack,

Ditambah dengan dua unsur, untuk menangani stack:

Dengan fungsi transisinya adalah

${\displaystyle \delta :Q\times (\Sigma \cup \{\epsilon \})\times \Gamma )\rightarrow Q\times \Gamma ^{*}}$              adalah fungsi transisi

Fungsi Automata dalam Hubungan dengan Bahasa:

1. Fungsi Automata sebagai pengenal (Recognizer) string-string dari suatu bahasa, dalam hal ini bahasa sebagai masukkan dari automata

2. Fungsi Automata sebagai pembangkit (Generator) string-string dari suatu bahasa, dalam hal ini sebagai keluaran dari automata 3. Rangkuman Himpunan, Relasi, dan Fungsi

3. Rangkuman Himpunan, Relasi, dan Fungsi

a. Himpunan

Himpunan adalah kumpulan benda atau objek yang dapat didefinisikan dengan jelas. Benda atau Objek dalam himpunan disebut elemen atau anggota himpunan. Dari definisi tersebut, dapat diketahui objek yang termasuk anggota himpunan atau bukan.

       Jenis-jenis Himpunan :

1. Himpunan bagian (ACB)

2. Himpunan Kosong ( {} )

3. Himpunan Semesta ( U atau S )

4. Himpunan Sama (A=B)

5. Himpunan Lepas

6. Himpunan Komplemen

7. Himpunan Ekuivalen

b. Relasi 

    Relasi dapat diartikan sebagai hubungan. Misalkan sebuah relasi menyatakan hubungan perkalian. Hasil relasi tersebut dapat dinyatakan dalam himpunan pasangan terurut x dan y dan dapat juga digambar pada bidang kartesius.

Cara menyatakan hasil relasi perkalian antara himpunan A dan B dapat dilihat pada contoh permasalahan di bawah.

  

  

c. Fungsi

Fungsi atau yang sering disebut juga dengan pemetaan masih termasuk dalam relasi. Suatu relasi disebut fungsi jika semua anggota himpunan daerah asal dipasangkan tepat satu ke daerah kawannya.

Simbol fungsi yang memetakan himpunan A ke B adalah

  

4. Rangkuman Simbol, Abjad, dan String

a. Simbol

Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol. Pada umumnya kita menggunakan huruf kecil (lower case)atau angka untuk melambngkan simbol, dan huruf kecil diakhir alphabet khususnya w,x,y,z untuk melambangkan untai (String).

b. Abjad  

Alfabet/Abjad (adalah vocabulary) adalah himpunan terbatas simbol. 

Contoh :

• Alfabet Latin {A, B, C,….,Z}
• Alfabet Yunani {α, β, γ,…,ω} 
• Alfabet Biner {0,1}

        c. String

String, dalam bahasa pemrograman komputer, adalah deretan simbol. Tipe data String adalah tipe data yang digunakan untuk menyimpan barisan karakter.

Tipe-tipe Bahasa String dalam Bahasa Pemrograman :

1. Bahasa Pascal
2. Bahasa C
3. Bahasa C++
4. Bahasa PHP