SOAL TEORI BAHASA DAN AUTOMATA (Mesin Pengenal Bahasa)

 

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, 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* 

Posted in: Catatan,Materi Ilkom