TEORI BAHASA DAN AUTOMATA

TEORI BAHASA DAN AUTOMATA

Beberapa terminologi dasar dari sebuah teori bahasa diantaranya:
- Alphabet
- Concatination / penyambungan
- String
Dalam teori bahasa, Istilah huruf = karakter = simbol dan istilah kalimat = kata = string.
• Simbol / huruf / karakter
Merupakan sebuah elemen alphabet yang memiliki makna unik / tunggal, misalnya symbol A dan symbol B yang memiliki makna berbeda.
• Alphabet
Dilambangkan dengan huruf capital miring, alphabet adalah himpunan tak kosong yang berhingga dari symbol – symbol.
• Kata / kalimat / String
Kata merupakan dereten symbol –simbol dari suatu alphabet

Contoh :
C = {a,b,c,1,2,3}
* Contoh diatas merupakan contoh sebuah alphabet C yang memiliki 6 buah symbol
* Contoh sebuah kata / string dari alphabet C: acca, back, 132, a12, dst.
* Kata acca dengan caac memiliki makna yang berbeda.
* Kata acca, 121, abba memenuhi aturan palindrome (walaupun kata dibalik memiliki makna yang sama).

*Dasar-dasar teori bahasa dan automata

Teori bahasa dan automata merupakan salah satu komponen ilmu informatika, teori ini merupakan ide dan model fundamental yang mendasari sebuah system komputasi, teori ini juga bisa disebut sebagai sebuah teknik rekayasa untuk perancangan system komputasi.

Beberapa bidang ilmu lain yang mendukung pengembangan metode komputasi :

1. Biologi
Mempelajari jaringan neuron yang mengilhami ditemukanannya finite automata.
2. Rangkaian Elektronika
Mempelajari teori switching sebagai perancangan perangkat keras menggunakan finite automata.
3. Matematika
Mengembangkan system logika yang berguna untuk masalah pembuktian automata.
* Beberapa model komputasi dalam automata:

1. Finite automata (FA)

Sering juga disebut dengan Finite State Automata (FSA). Terdiri dari Deterministic Finite Automata (DFA) dan Non Deterministik Finite Automata (NDFA). Teori dasar dari FA sangat umum yaitu system pada saat berada di salahsatu state dari sejumlah state bergerak diantara state-state secara dapat diproduksi yang bergantung pada masukan ke system. Salah satu penerapannya adalah kompilasi/translasi bahasa pemograman tingkat tinggi menjadi bahasa mesin yang ekivalen. Finite automata merupakan jenis otomata yang tidak memiliki memori sementara, FA adalah kelas mesin dengan kemampuan paling terbatas.

2. Pushdown Automata (PA)

Terdiri dari Deterministic Pushdown Automata (DFA) dan Non Deterministik Pushdown Automata (NDFA). PA memiliki memori sementara dengan mekanisme stack LIFO (Last In First Out).
3. Turing Machine (TM).
Memiliki mekanisme Random Access Memory.


- 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 = V2 ----> Panjang string = 2
VoVoV = V2oV=V3 -> Panjang string = 3
VoVoVoV = N4 ----> Panjang string = 4
VoVoVo...oV=Vn ---> Panjang string = n


Vk = 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+ = V1 U V2 U V3 U ... (Positive closure)
adalah himpunan string pada V, tidak ada string kosong didalamnya.

V0 = {ε}
adalah himpunan yang isinya hanya string kosong, dimana String kosong ε tidak sama dengan himpunan kosong �


Maka 'bbba' dapat ditulis 'b3a'


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

 Sejarah Otomata dan Teori Bahasa

Otomata bermula sebelum komputer ada pada teori di bidang sistem logika matematika atau formal, ilmuwan David Hilbert telah mencoba menciptakan algoritma umum untuk pembuktian (seluruh) persoalan matematika secara otomatis yaitu mampu menentukan salah benarnya sembarang prosisi matematika.

Tahun 1931, Kurt G�del mempublikasikan teori ketidaklengkapan dimana membuktikan prosedur/algoritma yang dikehendaki David Hilbert tersebut tidak akan pernah ada.

G�del membangun rumus di kalkulus predikat yang diterapkan pada bilangan bulat yang memiliki pernyataan-pernyataan definisi yang tidak dapat dibuktikan maupun dibantah di dalam sistem logika yang mungkin dibangun manusia.

Formalisasi argumen teorema ketidaklengkapan G�del ini berikut penjelasan dan formalisasi selanjutnya dari prosedur efektif secara intuisi merupakan salah satu pencapaian intelektual terbesar abad 20, yaitu abad dimana formalisasi berkembang semarak.

Pengembangan teori otomata, komputasi dan teori bahasa berikutnya difasilitasi perkembangan bidang psyco-linguistic. Bidang psyco-linguistic berupaya menjawab pertanyan-pertanyan berikut:

- Apakah bahasa secara umum?
- Bagaimana manusia mengembangkan bahasa?
- Bagaimana manusia memahami bahasa?
- Bagaimana manusia mengajarkan bahasa ke anak-anaknya?
- Apa gagasan-gagasan yang dapat dinyatakan dan bagaimana caranya?
- Bagaimana manusia membangun kalimat-kalimat dari gagasan-gagasan yang berada di pikirannya?

Sekitar tahun 1950-an, Noam Chomsky menciptakan model matematika sebagai sarana untuk mendeskripsikan bahasa serta menjawab pertanyaan-pertanyaan di atas. Saat ini dimulai pendalaman bidang bahasa komputer.

Perbedaan antara bahasa komputer dan bahasa manusia adalah sampai sekarang belum diketahuinya bagaimana cara manusia mengartikan bahasa, sementara dengan pasti dapat mengartikan bahasa pada komputer.

Noam Chomsky mengemukakan perangkat format disebut grammar untuk memodelkan properti-properti bahasa.

Grammar berisi sejumlah aturan serta menspesifikasikan bahasa tertentu.

Bahasa berisi semua string yang dapat dihasilkan menggunakan aturan-aturan grammar.

Meski pembahasan Chomsky terutama ditujukan untuk bahasa alami, grammar mempunyai nilai/manfaat sangat besar di ilmu informatika/komputer karena pencapaian ini digunakan untuk mendeskripsikan dan mendefinisikan sintaks bahasa pemrograman dan bahasa-bahasa formal lainnya.

Grammar diterapkan pada perancangan kompilator dan bidang-bidang di ilmu komputer.

McCulloch dan Pitts mengemukakan Mesin Abstrak sederhana yaitu finite automata untuk memodelkan neuron nets.

Finite automata juga digunakan untuk merancang switching circuit. Studi mengenai teori otomata terkait bidang-bidang lain di ilmu komputer.

Kemudian ekivalensi antara finite automata dan ekspresi reguler (reguler expression) dikemukakan Stephen Kleene. Sejak saat itu teori bahasa dikaitkan secara erat dengan teori bahasa formal. ubungan teori otomata dan teori pengkodean (coding theory) juga banyak diteliti.

Turing machine seperti komputer modern saat ini dapat mengolah (simbol-simbol di tape) dan mengahasilkan keluaran (simbol-simbol yang berada di tapenya setelah berakhirnya sebarisan pergerakkan) merupakan karya teoritis dari Alan Turing.

Karena banyak yang berperan pada pengembangannya, bidang teori ini diberi aneka ragam nama yaitu:
- teori otomata (theory of automata)
- teori bahasa formal (theory of formal language)
- teori mesin turing (theory of Turing machine).