BAB I
PENDAHULUAN
Sumber :DRS. JANOE HENDARTO MKOM.
Teori Bahasa
- Teori bahasa membicarakan bahasa formal (formal language), terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor).
- Bahasa formal adalah kumpulan kalimat. Semua kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama.
- Sebuah bahasa formal bisa dibangkitkan oleh dua atau lebih tata bahasa berbeda.
- Dikatakan bahasa formal karena grammar diciptakan mendahului pembangkitan setiap kalimatnya.
- Bahasa Natural/manusia bersifat sebaliknya; grammar diciptakan untuk meresmikan kata-kata yang hidup di masyarakat. Dalam pembicaraan selanjutnya ‘bahasa formal’ akan disebut ‘bahasa’ saja.
Otomata (Automata)
- Otomata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.
Beberapa Pengertian Dasar :
· Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol.
· String adalah deretan terbatas (finite) simbol-simbol. Sebagai contoh, jika a, b, dan c adalah tiga buah simbol maka abcb adalah sebuah string yang dibangun dari ketiga simbol tersebut.
· Jika w adalah sebuah string maka panjang string dinyatakan sebagai ïwï dan didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut. Sebagai contoh, jika w = abcb maka ïwï= 4.
· String hampa adalah sebuah string dengan nol buah simbol. String hampa dinyatakan dengan simbol e (atau ^) sehingga ïeï= 0. String hampa dapat dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.
· Alfabet adalah hinpunan hingga (finite set) simbol-simbol
Operasi Dasar String
Diberikan dua string : x = abc, dan y = 123
· Prefik string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling belakang dari string w tersebut.
Contoh : abc, ab, a, dan e adalah semua Prefix(x)
· ProperPrefix string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling belakang dari string w tersebut.
Contoh : ab, a, dan e adalah semua ProperPrefix(x)
· Postfix (atau Sufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling depan dari string w tersebut.
Contoh : abc, bc, c, dan e adalah semua Postfix(x)
· ProperPostfix (atau PoperSufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling depan dari string w tersebut.
Contoh : bc, c, dan e adalah semua ProperPostfix(x)
· Head string w adalah simbol paling depan dari string w.
Contoh : a adalah Head(x)
· Tail string w adalah string yang dihasilkan dari string w dengan menghilangkan simbol paling depan dari string w tersebut.
Contoh : bc adalah Tail(x)
· Substring string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling depan dan/atau simbol-simbol paling belakang dari string w tersebut.
Contoh : abc, ab, bc, a, b, c, dan e adalah semua Substring(x)
· ProperSubstring string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling depan dan/atau simbol-simbol paling belakang dari string w tersebut.
Contoh : ab, bc, a, b, c, dan e adalah semua Substring(x)
· Subsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol dari string w tersebut.
Contoh : abc, ab, bc, ac, a, b, c, dan e adalah semua Subsequence(x)
· ProperSubsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol dari string w tersebut.
Contoh : ab, bc, ac, a, b, c, dan e adalah semua Subsequence(x)
· Concatenation adalah penyambungan dua buah string. Operator concatenation adalah concate atau tanpa lambang apapun.
Contoh : concate(xy) = xy = abc123
· Alternation adalah pilihan satu di antara dua buah string. Operator alternation adalah alternate atau ½.
Contoh : alternate(xy) = x½y = abc atau 123
· Kleene Closure : x* = e½x½xx½xxx½… = e½x½x
½x
½…
· Positive Closure : x
= x½xx½xxx½… = x½x½x½…
Beberapa Sifat Operasi
· Tidak selalu berlaku : x = Prefix(x)Postfix(x)
· Selalu berlaku : x = Head(x)Tail(x)
· Tidak selalu berlaku : Prefix(x) = Postfix(x) atau Prefix(x) ¹ Postfix(x)
· Selalu berlaku : ProperPrefix(x) ¹ ProperPostfix(x)
· Selalu berlaku : Head(x) ¹ Tail(x)
· Setiap Prefix(x), ProperPrefix(x), Postfix(x), ProperPostfix(x), Head(x), dan Tail(x) adalah Substring(x), tetapi tidak sebaliknya
· Setiap Substring(x) adalah Subsequence(x), tetapi tidak sebaliknya
· Dua sifat aljabar concatenation :
¨ Operasi concatenation bersifat asosiatif : x(yz) = (xy)z
¨ Elemen identitas operasi concatenation adalah e : ex = xe = x
· Tiga sifat aljabar alternation :
¨ Operasi alternation bersifat komutatif : x½y = y½x
¨ Operasi alternation bersifat asosiatif : x½(y½z) = (x½y)½z
¨ Elemen identitas operasi alternation adalah dirinya sendiri : x½x = x
· Sifat distributif concatenation terhadap alternation : x (y½z) = xy½xz
· Beberapa kesamaan :
¨ Kesamaan ke-1 : (x*)* = x*
¨ Kesamaan ke-2 : e½x = x½e = x*
¨ Kesamaan ke-3 : (x½y)* = e½x½y½xx½yy½xy½yx½… = semua string yang merupakan concatenation dari nol atau lebih x, y, atau keduanya.
Read More Teori bahasa dan OTomata Download
