Pengantar Teori Bahasa dan Otomata

"Pengantar Teori Bahasa dan Otomata"

1. Pengertian 

Bahasa = Bahasa bisa juga disebut sebagai rangkaian simbol-simbol yang mempunyai makna.

Otomata = Otomata merupakan suatu sistem yang terdiri atas sejumlah state, di mana state menyatakan informasi mengenai input. Otomata juga dianggap sebagai mesin otomatis (bukan mesin fisik) yang merupakan suatu model matematika dari suatu sistem yang menerima input dan menghasilkan output.       

          Hubungan di antara bahasa dan otomata adalah bahasa dijadikan sebagai input oleh suatu mesin otomata, selanjutnya mesin otomata akan membuat keputusan yang mengindikasikan apakah input itu diterima atau ditolak.

Misalnya, kita memiliki sebuah mesin sederhana yang menerima input kata dalam bahasa Indonesia, hal ini bisa dilihat pada gambar DISAMPING : 

Pada gambar di samping, bila mesin mendapat string input berikut : 

1.ada : diterima 

2.adu : diterima 

3.add : ditolak 

PENJELASAN :

1. Sebuah string input diterima bila mencapai state akhir / final state yang pada contoh diatas digambarkan dengan lingkaran ganda. 
2. Mesin ini memiliki 6 state yaitu { q0, q1, q2, q3, q4, q5 } yang merupakan himpunan state yang ada pada mesin tersebut. 
3. State awal dari mesin adalah q0. 
4. { q3, q4 }adalah himpunan state akhir atau final state. 
5. Sedangkan himpunan simbol input adalah {a, d, u}.

2. Konsep Teori Bahasa dan Otomata

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

B. Alpabet adalah himpunan simbol (karakter) tidak kosong dan berhingga. Alpabet dilambangkan dengan Σ.

C. String adalah deretan simbol dari alpabet dimana perulangan simbol diijinkan. 

Contoh : 

V = {a,b,c,d} 

String pada alpabet V antara lain -> 

 'a','abcd','bbba’ 

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

 Contoh: 

|ε| = 0 

|a| = 1 

|aa| = 2 

|aaa| = 3 

|aaab| = 4 

E. Empty String (null string) adalah string yang tidak mengandung simbol apapun. Lambangnya ϵ.

F. Regular Expression adalah cara untuk mengekspresikan bahasa dengan hanya menggunakan operasi :

-Concatenation (Penyambungan) Contoh : 

 'a' o 'b' = 'ab' 

-Superscript (Perkalian) 

VoV = VV = V2 

-Kleene closure (String Tanpa Simbol) 

ε mempunyai sifat identitas, yaitu: 

ε o x = x 

x o ε = x 

-Positif closure (Tidak Ada String Kosong Didalamnya) 

V + = V1 U V2 U V3 U ... V 0 = {ε}