Nama : Maulana Akhsan

Nim : 4611412010

Matkul: Teori Bahasa dan Automata

Latihan 3.1

1. Carilah seluruh string pada L((a|b)*b(a|ab)*) dengan panjang string kurang dari 4.

Jawab : {L((a|b)*b(a|ab)*) ,|x|= 4}

L((a|b)*b(a|ab)*) : himpunan string yang mengandung paling sedikit satu substring ‘b’

Dengan jumlah string kurang dari 4, maka maksimal dari 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’ }

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 }

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’ sebanyak genap }

Jawab : ekspresi regular dengan mengandung 0 sebanyak genap, bisa ada 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, dengan panjang 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)* = {ε|(aa| b)|(aaa|bb)|...}

(a*|b)* = (a|b) *

Maka terbukti, (a*|b)* = (a|b) *

2. (a|b*)* = (a|b)*

Jawab :

(a|b*)* = {ε|(a| bb)|(aa,|bbb)|...}

(a|b*)* = (a|b) *

Maka terbukti, (a|b)* = (a|b) *

3. (a* b)* a* = a* (b a*)*

Jawab :

(a* b)* a* = (ԑ|(ab)*|(ab*ab*|....)a*

=( ԑa*|(aba)*|(ababa)*|....)

=(a*|(aba)*|(abab)*)....)

=a*( ԑ|(ba)*|(baba)*|...)

= a* (b a*)*

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*