Soal beserta jawabannya.
1. Carilah seluruh string pada L((a|b)*b(a|ab)*) dengan panjang string kurang dari 4
Jawab :
L((a|b)*b(a|ab)*) : himpunan string
yang mengandung paling sedikit satu substring ‘b’
Dengan jumlah
string kurang dari 4, makamaksimaldari 3 digit
0 digit= -
1 digit = b
2 digit = ab; ba
3 digit = baa; aba; aab;
String pada
L((a|b)*b(a|ab)*) = b;ab;ba;aab;aba;baa;
.
2. Tentukan
ekspresi reguler pembentuk bahasa pada ∑= {a,b,c}, yaitu
a. L(r) = { w є
∑* | w memiliki tepat sebuah simbol ‘a’ }
b. L(r) = { w є
∑* | w mengandung tepat 3 buah simbol ‘a’}
c. L(r) = { w є
∑* | w mengandung kemunculan masing-masing simbol minimal satu kali}
Jawab :
a. L(r) = { w є
∑* | w memiliki tepat sebuah simbol ‘a’ }
Jawab :
r = a (b|c) (b|c)*
b. L(r) = { w є
∑* | w mengandung tepat 3 buah simbol ‘a’}
Jawab :
r = aaa (b|c) (b|c)*
c. L(r) = { w є
∑* | w mengandung kemunculan masing masing simbol minimal satu kali}
Jawab :
r = abc
3. Tentukan
ekspresi reguler pembentuk bahasa pada = {0,1}, yaitu
a. L(r) ={ w є
∑* | w diakhiri dengan string 01 }
b. L(r) ={ w є ∑
* | w tidak diakhiri dengan string 01 }
c. L(r) ={ w є ∑
* | w mengandung simbol ‘0’ sebanyak genap }
d. L(r) ={ w є ∑
* | kemunculan string ’00’ pada w sebanyak kelipatan 3 }
Jawab :
a. L(r) = { w
Î∑* | w diakhiridengan string 01 }
Jawab : (0|1)*01,
ekspresi regular diakhiri dengan 01
ER: 111101;00001;10101001;
b. L(r) ={ w Î∑* | w tidak diakhiri dengan
string 01 }
Jawab :ekspresi
regular tidak di akhiri dengan string 01
ER: 1110; 0011; 0110;
c. L(r) ={ w Î∑* | w mengandung simbol ‘0’
sebanyakgenap }
Jawab :ekspresi
regular dengan mengandung 0 sebanyak genap, bisaada 2, 4 ,6, ….
Mengandung 0
sebanyak 2, ER: 1010;
Mengandung 0 sebanyak 4, ER :
011000; 00001;0000;
Mengandung 0 sebanyak 6, ER :
001001001;
d. L(r) ={ w Î∑* | kemunculan string ’00’
pada w sebanyak kelipatan 3 }
4. Tentukan ekspresi reguler pembentuk
bahasa pada ∑ = {a,b}, yaitu L(r) = { w є ∑* | |w| mod 3 = 0 }
Jawab :
Membuat contoh
ekspresi regular yang terdiri dari {a,b} dengan panjang string kelipatan 3,
karna |w| mod 3 = 0.
Maka,
denganpanjang string 3 = ER: aba; aab; bba; bab;….
Jika dengan
panjang string 6= ER; aabbab; babbaa; abbaab;……
Jika dengan
panjang string 9= ER: aababaaab; babbaabba;…..
Dan seterusnya ,…
Latihan 3.2
Buktikan kesamaan
ekspresi regular berikut :
1. (a*| b)* = (a
| b)*
Jawab :
(a|b)* = {ε,
"a", "b", "aa", "ab", "ba",
"bb", "aaa", ...}
Dengan diketahui a*= ε| a| aa| aaa| aaaa| …..,
Sedangkan b* = ε|b|bb|bbb|bbbb|…
Jadi(a|b)* yang
merupakan gabungan concate dari a* dan b* maka
(a|b)* =(ε | a| b|
aa| ab| ba| bb | aaa| ...)
Dengan diketahui: a*= ε| a| aa| aaa| aaaa| …..,
Maka(a*|b)* = (ε|
a| aa| aaa| aaaa| …..|b)*
= (ε| a|b | aa|bb | aaa|bbb | aaaa| bbbb …..)
Maka terbukti, (a*|b)* = (a|b)*
2. (a | b*)* = (a
| b)*
Jawab :
Diketahui (a|b)*
= ε| a| b| aa| bb| aaa| bbb| ab|
abb| aab| ba ....
Dengan b*
= ε| b| bb| bbb| bbbb| …..
(a|b*)= (a| ε| b| bb| bbb| bbbb| …..)
Maka (a|b*)* = (a|
ε| b| bb| bbb| bbbb| …..)*
= ε| a| b| aa| bb| aaa| bbb| ab| abb| aab| ba ....
Maka terbukti, (a|b*)*
= (a|b)*
3. (a* b)* a* =
a* (b a*)*
Jawab : Dengan a* = ε| a| aa| aaa| aaaa| …..
· (a b)*= (eï(ab)ï(abab)ï…)
maka (a*
b) = (ε b| ab| aab| aaab| aaaab|
…..,)
= (b| ab| aab| aaab| aaaab|...)
(a* b)* =
(b| ab| aab| aaab| aaaab|...)*
= (eïa|b | abïaabï…)
(a* b)* a*
=(eïa|b | abïaabï…) a*
= (eïa|b | abïaabï…) (ε| a| aa|
aaa| aaaa| …..)
= (e | a | b | aa | aaa | ab | aab | …)
· (b a)*= (eï(ba)ï(baba)ï…)
Maka (b a*)* =
(eï(ba)ï(baba)ï…) *
= (eïb | a | ba ïbaaï…)
a* (b a*)* =
a* (eïa|b | abïaabï…)
= (ε| a| aa| aaa| aaaa| …..) (eïb | a | ba
ïbaaï…)
= (e | a |
b | aa | aaa | ab | aab | …)
4. (a a*) ( є | a) = a*
Jawab :
Dengan diketahui a* = ε| a| aa| aaa| aaaa| …..,
Dan (a a*) =
a(ε| a| aa| aaa| aaaa| …..) (ԑ|a)
= (ε a| aa|
aaa|aaaa|…) (ԑ|a)
=
(a|aa|aaa|aaaa|…) (ԑ|a)
= (ε| a| aa| aaa| aaaa| …..) =>a*
Maka terbukti, (a a*) (ԑ|a) = a*
Tidak ada komentar:
Posting Komentar