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
- 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 adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.
kumpulan
kalimat. Semua kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata
bahasa (grammar) yang sama.
Otomata (Automata)
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.
Tags
Kuliah