Konsep TBO Dan Operasi Dasar String
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
½…
½x½…
·
Positive Closure : x
= x½xx½xxx½…
= x½x½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*
= 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.
