Institute Teknologi PLN Jakarta
Dosen : Dine Tiara Kusuma S.T., M.Kom
Teori Bahasa dan Otomata di
Sertai Chomsky Hierarchy
Halo temen-temen semua, kali ini kita akan membahas mengenai Teori bahasa dan Otomata disertai Chomsky Hierarchy . Bagi kalian yang mahasiswa Teknik Informatika kemungkinan dapet mata kuliah ini nih. Oke jadi pada blog ini kita bakal bahas dari awal ya, kita kenalan dulu dengan apa itu Teori Bahasa dan apa itu Otomata.
Pengertian Dasar
Teori bahasa dan otomata adalah dasar dari teknik kompilasi, tapi apa itu teori bahasa? dan apa itu otomata?
Bahasa
Bahasa disebut sebagai rangkaian simbol - simbol yang mempunya makna.
Otomata
- Otomata merupakan suatu sistme 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 menghasilkanb output.
Bahasa dan Otomata
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 data dalam bahasa Indonesia, hal ini dapat dilihat pada gambar disamping.
Pada gambar disamping, bila mesin mendapat string input berikut.
Ada : diterima, Add : ditolak, Adu : diterima
Penjelasan pada diagram
Konsep Teori Bhasa dan Otomata
- Teori Bahasa adalah konsep-konsep pada “string alpabet” dalam penyambungan karakter-karakter alpabet untuk membentuk suatu makna (bahasa).
- Alpabet adalah himpunan simbol (karakter) tidak kosong dan berhingga. Alpabet dilambangkan dengan ∑
- String adalah deretan simbol dari alpabet dimana perulang simbol diijinkan. Contoh : V = (a,b,c,d) string pada alpabet V antara lain ->’a’,’abcd’,’bbba’
- Panjang String adalah jumlah simbol di dalam string bukan pada alpabet dan pengulangan.
- Empty String (null string) adalah string yang tidak mengandung simbol apapun. Lambangnya ε atau λ
- Regular Exspression adalah cara untuk mengekspresikan bahasa dengan hanya menggunakan operasi :
o Concatenation (penyambung)
o Superscript (perkalian)
o Kleene closure (string tanpa simbol )
o Positif closure (tidak ada string kosong dalamnya )
Chomsky Hierarchy
Secara umum tata bahasa dirumuskan sebagai berikut :
ɑ => β, yang berarti ɑ menghasilkan β, atau ɑ menurunkan β.
- Simbol Variabel (Non Terminal) adalah simbol yang masih bisa diturunkan dan ditandai dengan huruf besar seperti A, B, C, dst.
- Simbol Terminal adalah simbol yang sudah tidak bisa diturunkan dan ditandai dengan huruf kecil seperti a, b, c, dst.
Contoh Aturan Produksi
- T => ɑ (dibaca "T menghasilkan a")
- E => T | T + E (dibaca "E menghasilkan T" atau "E menghasilkan T dan E")
- Simbol | menyatakan 'atau', digunakan untuk mempersingkat penulisan aturan produksi yang mempunyai ruas kiri yang sama.
o Tipe 0 / Unrestricted / Natural Language
Aturan :
- Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variabel.
- Tidak ada batasan pada aturan produksinya.
Contoh :
Abc => De (diterima)
ABC => b (diterima)
abc => GHI (ditolak, karena simbol pada sebelah kiri tidak ada sebuah simbol variabel)
o Tipe 1 / Konteks
Sensitive
Aturan :
- Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variabel.
- Panjang string pada ruas kiri <= panjang string pada ruas kanan. |ɑ| <= |β|.
Contoh :
Ab => DeF (diterima)
CD => eF (diterima) exception : S => ɛ (diterima)
ABC => DE (ditolak, karena jumlah simbol pada ruas sebelah kiri lebih banyak dari jumlah simbol pada ruas kanan)
o Tipe 2 / Bebas Konteks /
Context Free
Aturan :
- Simbol pada sebelah kiri harus berupa sebuah simbol variable
Contoh :
B => CDeFG (diterima)
D => BcDe (diterima)
a => b (ditolak, karena simbol pada sebelah kiri harus berupa sebuah simbol variabel)
o Tipe 3 / Reguler Aturan
Aturan :
- Simbol pada sebelah kiri harus berupa sebuah simbol variable
- Simbol pada sebelah kanan maksimal hanya memiliki sebuah simbol variabel dan bila ada terletak di posisi paling kanan.
Contoh :
A => e (diterima)
A => fgh (diterima)
A => eH (diterima)
C => D (diterima)
A => Bc (ditolak, karena simbol variabel pada sebelah kanan harus berada pada posisi paling kanan)
