Pengantar Teori Bahasa dan Otomata

        

Pengantar

"Teori Bahasa dan Otomata"


Ilmu komputer memiliki dua komponen utama yaitu model dan gagasan tentang komputasi dan teknik rekayasa untuk perancangan sistem komputasi (perangkat keras dan perangkat lunak). Tujuan mempelajari Teori Bahasa dan Otomata yaitu mengetahui dan mempelajari dasar-dasar teori bahasa formal dan model-model mesin matematis yang menggambarkan prinsip kerja komputer.

  • Definisi Bahasa dan Otomata

           Bahasa adalah rangkaian simbol-simbol yang mempunyai makna. Bahasa merupakan kumpulan string-string dari sumbol-simbol untuk suatu alfabet. String sendiri merupakan suatu kata (gabungan dari huruf). Otomata dapat diartikan sebagai Mesin Abstrak dengan model matematika, dimana sistemnya menerima input dan menghasilkan output, serta terdiri dari sejumlah state (tempat).
         
        Bahasa sebagai input oleh suatu mesin otomata, selanjutnya mesin otomata akan membuat keputusan yang mengidentifikasikan apakah input diterima atau tidak (ditolak). Sebagai Contoh penerapan mesin otomata, misalnya kita akan memodelkan mesin otomata yang hanya dapat menerima inputan dalam bahasa inggris. Apabila digambarkan pemodelan bahasanya akan menjadi : 

Mesin Otomata Penerima Input Bahasa Inggris

Pada gambar diatas merupakan mesin otomata yang hanya dapat menerima inputan berupa bahasa inggris, jika mesin mendapatkan string inputan :
  • dengan     : di tolak
  • deny          : diterima
  • dentist      : diterima
Suatu string dikatakan diterima apabila mencapai state akhir (ditandai dengan lingkaran ganda) untuk kasus ini ada pada q7 dan q11. State awal selalu diawali oleh panah tanpa inputan (State q0).
  • Hirarki Chomsky

         Tata Bahasa (grammer) didefinisikan sebagai kumpulan dari himpunan-himpunan variabel, simbol-simbol terminal, simbol awal yang dibatasi oleh aturan produksi. Pada tahun 1959, Noam Chomsky menggolongkan tingkatan bahasa menjadi empat yang disebut Herarki Chomsky. Pengelompokan tersebut dapat dilihat pada tabel berikut.

    Suatu aturan produksi dapat dinyatakan dalam bentuk alpa->beta (dibaca : alpa menghasilkan beta atau dibaca : alpa menurunkan beta). Dimana : alpa menyatakan simbol-simbol pada ruas kiri aturan produksi dan beta menyatakan simbol-simbol pada ruas kanan aturan produksi (hasil produksi). 

Beberapa istilah dalam aturan produksi :

  • Simbol Variabel/nonterminal : simbol yang masih dapat diturunkan, biasanya dilambangkan menggunakan abjad kapital ('A', 'B' , dll).
  • Simbol terminal : simbol yang tidak dapat diturunkan kembali, biasanya dilambangkan menggunakan abjad non-capital ('a', 'b', dll).

Contoh-Contoh aturan produksi untuk setiap level bahasa:

1. Tipe 0 (Natural Language)*

Bahasa manusia termasuk kedalam ttipe ini, dimana tidak ada batasan untuk aturan produksinya. Aturan :

  1. Simbol sebelah kiri harus minimal ada sebuah simbol variabel
  2. Tidak ada batasan pada aturan produksi

 Contoh :

  • Abc  -> aa
  • Bc -> aBaB
  • Aab -> aaBaaBa
2. Tipe 1 (Contex Sensitive)*

Aturan :
  1. Panjang string di ruas kiri (alpa) tidak lebih panjang atau sama dengan panjang string sebelah kanan 
  2. Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variabel 
Contoh :
  • Ab -> aBa
  • cD -> aB
  • dEd -> FabCa
3. Tipe 2 (Bebas Konteks)*

Aturan :
  1. alpa adalah sebuah simbol variabel, dan batasanya bertambah bahwa ruas kiri harus tetap satu simbol variabel. 
Contoh :
  • A -> aa
  • B -> aBD
  • C -> FGab
4. Tipe 3 (Reguler)*

Aturan : 
  1. Ruas kanan maksimal memiliki sebuah simbol variabel yang terletak paling kanan. Artinya bisa memiliki simbol terminal dengan jumlah tidak dibatasi, tetapi bila terdapat simbol variabel maka simbol variabel tersebut hanya berjumlah satu (1) dan terletak paling kanan.
  2. Simbol sebelah kiri harus berupa simbol variabel
Contoh :
  • A -> aa
  • B -> aaB
  • C -> aaaaaa

Kesimpulannya : Bahasa tipe 3 sudah termasuk bahasa tipe 2,1, dan 0. Bahasa tipe 2 sudah termasuk bahasa tipe 1, dan 0. Juga bahasa tipe 1 pasti termasuk tipe 0.


Comments

Post a Comment