Teori Bahasa dan Automata

Teori Bahasa Formal

• Pembentukan struktur sebuah bahasa diawali dengan memakai sebuah finite set (himpunan terbatas), dimana unit fundamentalnya disebut alphabet (S)
• String-string yang boleh ada di dalam sebuah bahasa disebut word
• Contoh language adalah Bahasa Indonesia. Alphabet yang biasa dipakai adalah huruf, koma dan titik. Semuanya dispesifikasi seperti di bawah ini: 

S = {a b c d e ... z , . }

• Bila language ini dinamakan KATA-INDONESIA, dimana semua string adalah word/kata di dalam kamus, maka definisinya adalah:

KATA-INDONESIA = {semua kata di dalam kamus}

• Contoh sederhana suatu language dengan alphabet yang ada hanya sebuah huruf, yaitu huruf x

S = { x }

L = { x xx xxx xxxx ... }

• Simbol alphabet tidak harus alphabet huruf latin, namun dapat berisi apa saja
• Sebuah string dimungkinkan tidak punya alphabet. String ini disebut empty string atau null string dan dilambangkan L. Perlu diingat L bukan alphabet dalam language

Contoh: L = { L x xx xxx xxxx ... }

• Bahasa tanpa word dilambangkan dengan null set q
• Tolong dibedakan antara language tanpa word dengan word yang mempunyai L

L = { x xx xxx }

L ¹ L + { L }

L = L + q

• Contoh sebuah bahasa dengan non empty string

L1 = { x xx xxx xxxx ... }

Atau dengan cara lain

L1 = { xn for n = 1 2 3 ... }

• Dalam language L1, dapat dilakukan operasi penggabungan (concatenation) dari word yang ada menjadi word baru. Contoh

word xx dengan word xxx digabung menjadi word baru xxxxx

• Tidak selalu benar bila dua word digabungkan akan membentuk sebuah word baru. Contoh:

L2 = { x xxx xxxxx xxxxxxx ... }

= { x ganjil}

= { x 2n+1 for n = 0 1 2 3 }

xxx dan xxxxx adalah word pada language L2, namun  pengabungannya bukanlah word di dalam L2

• Didefinisikan suatu fungsi length untuk menghitung jumlah huruf di dalam sebuah word

length(xxxxxx) = 6 length(7152) = 4

length(L) = 0

• Bila diinginkan sebuah language mempunyai null string, maka jangan lupa untuk memasukannya saat mendefinisikan language tersebut

L4 = { L x xx xxx xxxx ... }

= { xn for n = 0 1 2 3 }

• Harap dipahami bahwa x0 = L dan bukannya x0 = 1 seperti di aljabar
• Didefinisikan fungsi reverse. Reverse dari suatu string adalah string yang sama tetapi tersusun dari belakang, walaupun string ini bukanlah word dalam bahasa tersebut

reverse(xxx) = xxx                           reverse(xxxxx) = xxxxx

reverse(145) = 541                           reverse(140) = 041

• Didefinisikan suatu language yang disebut PALINDROME dari alphabet

S = { a, b}

PALINDROME = { L, dan semua string x sedemikian sehingga reverse(x) = x }

maka akan diperoleh:

PALINDROME = { L a b aa bb aaa aba bab bbb aaaa abba ... }

• Diketahui alphabet S, diinginkan untuk mendefinisikan sebuah language dimana tiap string dari huruf yang ada di dalam S adalah sebuah word, termasuk null string Language ini disebut sebagai closure Dapat dinotasikan dengan menambah sebuah asterisk sesudah nama  dari alphabet è S* (Kleene Star)

Contoh:

Jika S = { x } maka

S* = L4 = { L x xx xxx ... }

Jika S = { 0 1 } maka

S* = { L 0 1 00 01 10 11 000 001 ... }

Jika S = { a b c } maka

S* = { L a b c aa ab ac ba bb bc ca cb cc aaa ... }

• Operasi Kleene Star menghasilkan infinite language dari string huruf yang ada pada alphabet
• Yang dimaksud infinite language adalah tak terhitung banyaknya word Disarankan word dari language tersusun urut dari yang pendek secara alphabetik

Contoh:

Jika S = { aa, b} maka

S* = { L dan word bentukan yang berasal dari aa dan b }

S* = { L dan semua string bentukan dari a dan b dengan a yang selalu berderet dalam jumlah yang genap)

= { L b aa bb aab baa bbb aaaa aabb baab bbaa bbbb aaaab aabaa aabbb baaaa baabb bbaab bbbaa ... }

• String aabaaab tidak termasuk S* karena jumlah a tidak genap

Contoh:

Jika S = { a, ab } maka

S* = { L dan word bentukan yang berasal dari a dan ab }

S* = { L dan semua string bentukan dari a dan b kecuali yang dimulai dengan b dan yang mengandung dua b berdempetan }

= { L a aa ab aaa aab aba aaaa aaab aaba abaa abab aaaaa aaaab aaaba aabaa aabab abaaa abaab ... }

Buat teman-teman yang mungkin belum punya materi Teori Bahasa dan Automata, ini ada file untuk didownload, materi saya dapatkan langsung dari Bu Mei Lestari S.Kom Dosen Teori Bahasa dan Automata UNINDRA.

DOWNLOAD FILE LENGKAP