Dunia Komputer

Teori Bahasa dan Automata

Bahasa adalah struktur yang dikendalikan sekumpulan aturan tertentu, semacam mesin untuk memproduksi makna. Akan tetapi seperti setiap mesin hanya terdapat kemungkinan terbatas bagi setiap orang dalam menggunakannya.

Dalam bahasa disediakan pembendaharaan kata atau tanda (vocabulary), serta perangkat aturan bahasa (grammar, sintaks) yang harus dipatuhi jika hendak menghasilkan sebuah ekspresi yang bermakna.  

Proses Kemampuan Pemahaman Bahasa
 
Hipotesis Noam Chomsky menggugat postulat John Locke (tokoh empirisme) yang menyatakan segala pengetahuan yang dimiliki manusia berasal dari rangsangan-rangsangan luar (pengalaman) yang ditangkap oleh indera-indera manusia, sehingga meniadakan pengetahuan apriori (pengetahuan yang langsung tertanam di manusia)

Noam Chomsky menyandarkan pada pemahaman bahasa sebagai sesuatu yang bersifat khas dan bawaan (tertanam) pada manusia sejak lahir.

Secara khusus Chomsky dipengaruhi Descartes tentang bahasa dan pikiran yang terikat begitu erat sehingga pengetahuan tentang bahasa bisa membuka pengetahuan tentang pikiran manusia.

Secara mendasar bahasa adalah bagian psikologi manusia yang dipahami sebagai teori tentang kemampuan pikiran manusia berupa ungkapan dari subjek psikologi.

Chomsky dan para ahli bahasa telah mengamati anak kecil mampu menjadi lancar berbahasa lebih cepat dan mudah dibanding "algoritma belajar berbahasa". 

Teori Bahasa
 Teori Bahasa adalah konsep-konsep pada "string alpabet V" dalam penyambungan 
karakter-karakter alpabet untuk membentuk suatu makna (bahasa).

- Alpabet

Adalah himpunan simbol (karakter) tak kosong yang berhingga. Alpabet digunakan untuk membentuk kata-kata (string-string) di bahasa. Bahasa dimulai dengan alpabet. Pada beberapa buku, alpabet dilambangkan dengan Σ Istilah huruf, karakter dan simbol adalah sinonim menunjukkan elemen alpabet. Jika simbol berbaris bersebelahan, maka diperoleh "string simbol". Istilah kalimat, kata dan string adalah sinonim

Contoh : 

{a,b} -> Himpunan yang terdiri dari simbol "a" dan "b".

- Penyambungan (Concatenation - o)

Penyambungan dilakukan pada 2 karakter atau lebih membentuk 1 barisan karakter (string simbol).

'a' o 'b' = 'ab'

'ab' o 'baab' = 'abbaab'

- String pada alpabet V


Karakter atau barisan karakter pada alpabet V dibentuk dari penyambungan karakter pada alpabet V.
String pada alpabet V adalah deretan (sekeun) simbol dari V dimana perulangan simbol diijinkan.

Contoh :

V = {a,b,c,d}

String pada alpabet V antara lain -> 'a','abcd','bbba'


Pemangkatan

Penyambungan dapat dianggap sebagai perkalian karena biasanya penulisannya adalah bila x dan y string, maka x o y adalah xy. sehingga pemangkatan dapat digunakan

VoV = VV = V² ----> Panjang string = 2
VoVoV = V²oV=V³ -> Panjang string = 3
VoVoVoV = N⁴ ----> Panjang string = 4
VoVoVo...oV=Vⁿ ---> Panjang string = n


V^k = VoVoVo...oV
adalah himpunan string dengan panjang k, masing-masing simbol adalah alpabet V

V^* = {ε} U V⁺ (Kleene closure)
adalah string pada V, termasuk string kosong dimana ε string kosong (string tanpa simbol)

ε mempunyai sifat identitas, yaitu:
ε o x = x
x o ε = x

V⁺ = V¹ U V² U V³ U ... (Positive closure)
adalah himpunan string pada V, tidak ada string kosong didalamnya.

V⁰ = {ε}
adalah himpunan yang isinya hanya string kosong, dimana String kosong ε tidak sama dengan himpunan kosong.
Maka 'bbba' dapat ditulis 'b³a'

 
Panjang String

Panjang string dilambangkan |w| dimana panjang string adalah jumlah simbol di dalam string bukan pada alpabet dan pengulangan kemunculan simbol dihitung.

Contoh:

|ε| = 0
|a| = 1
|aa| = 2
|aaa| = 3
|aaab| = 4

Otomata

Otomata adalah mesin abstrak yang menggunakan model matematika, tetapi matematika yang digunakan benar-benar berbeda dibanding matematika klasik dan kalkulus. Model yang digunakan adalah model mesin state (state machine model) atau model trnasisi state (state transition model).


Terdapat 3 model komputasi pada teori otomata.

- Finite automata
- Pushdown automata
- Turing Mavhine

Memori Otomata

Otomata dibedakan berdasarkan jenis memori sementara yang dimilikinya, yaitu:
 
- Finite automata (FA)
Tidak memiliki memori sementara. Finite automata adalah kelas mesin dengan kemampuan-kemampuan paling terbatas.
 
- Pushdown automata (PDA)
 Memiliki memori sementara dengan mekanisme LIFO (Last In, First Out). Mesin ini lebih ampuh karena bantuan keberadaan stack yang dipandang sebagai unit memori
 
- Turing Machine (TM)
 Memiliki memori dengan mekanisme pengaksesan acak (Random akses memori). Turing 
 Machine merupakan model matematika untuk komputer saat ini.
Demikianlah ulasan tentang Teori Bahasa dan Automata.. Semoga bermanfaat untuk kita semua,, Terima kasih telah mengunjungi blog ini.