Konsep Bahasa
Simbol. Simbol
merupakan elemen unik terkecil dari bahasa. Dalam sebuah bahasa terdapat
sejumlah berhingga simbol-simbol.
Abjad / Alfabet. Merupakan himpunan dari simbol-simbol yang
digunakan dalam suatu bahasa. Biasanya dinotasikan dengan S. Misalkan S = {0,1}.
String / word / kata / untai. Adalah barisan berhingga dari
simbol-simbol dalam suatu alfabet. Misalkan :
S = {0,1} maka 01, 00, 111 merupakan
string yang dibentuk berdasarkan alfabet S. Dalam pembahasan, seringkali suatu
untai/string dinyatakan dengan suatu variabel, yang biasanya berupa huruf
kecil. Contoh : w = “01”; x = “aba”, dst.
Panjang String. Suatu string disusun dari sejumlah n
simbol, dengan n³0. Banyaknya simbol yang menyusun
sebuah string disebut panjang string, yang disimbolkan dengan |x|.
contoh : x = aba , maka |x| = 3.
Untai hampa. Sebuah
string dengan panjang nol (n=0) disebut untai hampa dan dinotasikan
dengan l. Untai hampa (l) merupakan untai yang dibentuk berdasarkan
abjad apa saja. Sehingga l merupakan himpunan bagian dari
sembarang himpunan.
Bahasa. Bahasa merupakan himpunan string/kata dari
alfabet bahasa itu. Misal untuk
-
S1 = {0,1} maka L1 = {00,01,11,111} merupakan bahasa yang dibentuk
berdasarkan abjad S1
.
-
S2 = {a,b} maka L2 = {a, ab, aab, aaab, … } merupakan bahasa
berdasarkan abjad S2
Misalkan S suatu abjad dan w adalah
untai yang dibentuk berdasarkan abjad S. Jika terdapat L yang merupakan
bahasa berdasar abjad S dan jika w ada di dalam L,
kita tuliskan w Î L, yang berarti w elemen
dari L.
Bahasa kosong. Merupakan bahasa yang tidak terdiri dari
untai apapun. Dinotasikan dengan {} atau Æ.
Bahasa Universal. Adalah bahasa yang terdiri dari semua kata
yang dapat dibentuk berdasarkan suatu abjad S. Misalkan S = {1} maka bahasa universal,
dinotasikan S*, adalah S* = {l, 1, 11, 111, 1111, …}
Operasi pada String
Perangkaian
(Concatenation). Jika w dan z
adalah untai, perangkaian w dengan z merupakan untai yang
diperoleh dengan merekatkan z ke w.
Contoh : w = “abang” dan z = “none” maka wz atau w.z
= “abangnone”. Panjang kata wz, |wz| = |w| + |z|=9.
Sebarang kata jika dirangkai dengan l, tidak akan merubah kata tersebut. wl=lw=w. Jadi l merupakan identitas (identity)
terhadap operasi perangkaian.
Pangkat (Exponentiation). Misalkan w merupakan sebuah
kata, untuk n Î bilangan asli, didefinisikan :
Misalkan , S = {0,1} dan w = 110, diperoleh :
w0 = l
w1 = w.w0
= 110.l = 110
w2
= w.w1 = 110.110 = 110110
w3
= w.w2 = 110.110110 = 110110110
Sama Dengan (Equal). Jika w dan z adalah
untai, dikatakan w sama dengan z jika keduanya terdiri dari
simbol-simbol yang sama dan panjangnya sama, dinotasikan w = z.
Awalan (prefix). Jika w dan x adalah
kata, maka x merupakan awalan dari w jika untuk suatu untai y,
berlaku w = xy. Contoh w = 121 dan x = 12, maka x
merupakan awalan dari w, dimana dalam hal ini y = 1.
Subuntai (substring). Sebuah untai w merupakan subuntai dari untai lain z
jika terdapat untai-untai x dan y, sehingga berlaku z = xwy.
Pembalikan (reversal / transpose). Transpose dari sebuah untai w,
yaitu wR, didefinisikan sebagai :
Contoh : w = “able”,
wR = (able)R = (ble)R
a
= (le)Rba
= (e)R lba
= (l)Relba
= l. elba
= elba
Operasi Pada Bahasa
Concatenation. Misal A dan B adalah bahasa berdasarkan suatu
abjad. Didefinisikan perangkaian dari bahasa A dan B sebagai :
A.B
= { w.x | w Î A dan x Î B}
Jadi A.B terdiri dari semua untai yang dibentuk
dengan mengambil setiap untai di A dan merangkaikannya dengan setiap untai di
B. Contoh : A = {bird, dog} dan B = { house} maka AB = {birdhouse, doghouse}
Eksponensiasi. Misalkan A bahasa berdasarkan
abjad S, didefinisikan :
Jadi, jika
misalkan A = {ab,a} berdasarkan abjad S = {a,b} maka :
A0 = { l }
A1 = A.A0 =
{ab,a}{l} = {ab,a}
A2 = A.A1 =
{ab,a}{ab,a} = {abab,aba,aab,aa}
A3 = A.A2 =
{ab,a}{abab,aba,aab,aa} = {ababab,ababa,abaab,abaa,aabab,aaba, aaab,aaa}
Gabungan (Union). Jika A dan B adalah bahasa
berdasarkan abjad S maka gabungan dari A dan B, A È B, terdiri dari semua kata yang muncul
sekurang-kurangnya sekali di dalam A dan B.
A
È B = {x | x Î A atau xÎB}
Irisan (intersection). Irisan dari bahasa A dan B terdiri
dari kata-kata yang muncul di A sekaligus di B. Dinotasikan sebagai : A Ç B,
A
Ç B = {x | x Î A dan x Î B}
Selisih (Difference). Jika A dan B bahasa berdasarkan
abjad S, didefinisikan selisih antara
bahasa-bahasa tersebut sebagai :
A
– B = {x | x Î A dan x Ï B}
Komplemen. Komplemen dari suatu bahasa A berdasarkan
abjad S didefinisikan sebagai : 
.
.
Subbahasa (sublanguage). Jika A dan B bahasa berdasarkan
abjad S, dan jika semua untai di A juga
merupakan untai di B maka A disebut subbahasa dari B. (A Í B)
Equal. Dua bahasa A dan B dikatakan sama atau equal,
A = B, jika kedua bahasa tersebut secara persis mempunyai untai-untai yang
sama.
Pembalikan (Transpose/Reversal). Pembalikan dari suatu bahasa A dapat
didefinisikan sebagai :
AR
= { xR | x Î A }
Contoh : A = { dog, bog} maka AR =
{god, gob}.
Kleene Closure / Star Closure. Jika A sebuah bahasa maka penutup
kleene dari bahasa A didefinisikan sebagai :
A* = 
.
.
Contoh : A = {a} maka A* = {l,a,aa,aaa,…}
Positive Closure / Plus Closure. Jika A sebuah bahasa maka penutup
kleene dari bahasa A didefinisikan sebagai :
A+ = 
.
.
Contoh : A = {a} maka A+ =
{a,aa,aaa,…}.
Teorema :
A+ = A. A* = A*. A
