Pertemuan II - Operasi Bahasa Formal [PDF]

Citation preview

Oleh : Ahmat Adil



















Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol. String adalah deretan terbatas (finite) simbolsimbol. Sebagai contoh, jika a, b, dan c adalah tiga buah simbol maka abcb adalah sebuah string yang dibangun dari ketiga simbol tersebut. String hampa adalah sebuah string dengan nol buah simbol. String hampa dinyatakan dengan simbol  (atau ^) sehingga = 0. Alfabet adalah hinpunan hingga (finite set) simbol-simbol











Panjang string x dituliskan dengan |x| Sebuah string dengan panjang n yang dibentuk dari himpunan A adalah barisan dari n symbol, a1a2...an ai  A Contoh : - Panjang untai 1011, ditulis |1011| = 4 - Panjang untai abcde, ditulis |abcde|=5 String kosong (null string), dilambangkan dengan  adalah untaian dengan panjang 0 dan tidak berisi apapun. contoh : Panjang untai λ , ditulis | λ | = 0



 







Operasi penyambungan (a.b) Operasi penggabungan (a+b) atau a U b Klenee Closure (r*)







Contoh : ◦ 0 x 1 = 0.1 = 01 ◦ a x b = a.b = ab ◦ a x b ≠ b x a karena a x b = ab sedangkan b x a = ba







0 + 1 = 0 U 1 atau 0 | 1 = 0,1 a + b = a U b atau a | b = a, b







Jadi a + b = b + a















a* = adalah himpungan nilai dari null sampai dengan jumlah simbol a tidak berhingga Jadi a* = λ, a, aa, aaa, aaa… Hasil diatas diperoleh dari : a0 = λ a1 = a a2 = aa a3 = aaa a4 = aaa ….. an =



1.



2. 3.



* Klenee closure Operasi Penyambungan (x) Operasi penggabungan (+)



Contoh : 1. 2 +3 x 5 = 2,35 Yang dioperasikan terlebih dahulu adalah 3x5 :35, sehingga menjadi 2+35  hasilnya menjadi 2,35 2. (2+3) x 5 = 25, 35 Didapat dari : 2 x 5 + 3 x 5 = 25, 35







  







Contoh lain : a+b* x c = a,c,bc,bbc,bbbc,… Hasil ini didapat dari : b* = ∧, b, bb, bbb, … b* x c = ∧ x c, b x c, bb x c, bbb x c = c, bc, bbc, bbbc, …. Maka : a+b* x c = a,c,bc,bbc,bbbc,…



       







(a+b)* x c = c, ac, bc, aac, abc, bac, bbc, … Hasil ini didapat dari : (a+b)* = ∧, a, b, aa, ab, ba, bb, …. (a+b)0= ∧ (a+b)1= a, b (a+b)2= (a+b) (a+b) = aa, ab, ba, bb (a+b)n= …. Maka : (a+b)* x c = c, ac, bc, aac, abc, bac, bbc, …



0 x 1 + 0 = 01, 0 0 x ( 1 + 0) = 01, 00 0 x ( 1 + 0)* = (1 + 0)* = λ, 1, 0, 11, 10, 01, 00, 111, 110, 101, 100, 011, 010, 001, 000 …. diperoleh dari (1 + 0)0 = λ (1 + 0)1 = 1, 0 (1 + 0)2 = (1 + 0) x (1 + 0) = 11, 10, 01, 00 (1 + 0)3 = (1 + 0) x (1 + 0) x (1 + 0) = 111, 110, 101, 100, 011, 010, 001, 000 ……….. (1 + 0 )n = Jadi 0 x ( 1 + 0)* = 0, 01, 00, 011, 010, 001, 000, 0111, 0110, 0101, 0100, 0011, 0010, 0001, 0000, …..



Tentukan nilai dari operasi berikut : (ab)* a Jawab (ab)* = ε, ab, abab, ababab, … (ab)* a = a, aba, ababa, abababa



Tentukan nilai dari operasi berikut : 1 (0+1)* + 10*



Jawab (0+1)*  (0+1)0 = ε (0+1)1 = 0, 1 (0+1)2 = (0+1)(0+1) = 00, 01, 10, 11 (0+1)3 = (0+1)(0+1) (0+1) = 000,001, 010,011, 100, 101, 110, 111 ……. 1(0+1)* = 1, 10,11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111,… 0* = ε, 0, 00, 000, 0000, 00000, …. 10* = 1, 10, 100, 1000, 10000, 100000, ….. Maka 1 (0+1)* + 10* = 1, 10, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, …..



Tentukan nilai dari operasi berikut : (a+c) b* Jawab : b* = ε, b, bb, bbb, bbbb, bbbbb, …… (a+c) b* = a, c, ab, cb, abb, cbb, abbb, cbbb, …..