er

Sunday 20 October 2013

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* 

Comments
0 Comments

0 comments:

Post a Comment

Berkomentarlah dengan kata-kata yang sopan, tidak spam, dan bijak ^.^
Terima Kasih telah berkunjung