UTS TBO 2016/2017

1.  Diberikan string (x) = aku , sebutkanlah;

a)      ProperPrefix (x)

b)      Postfix (x)

c)      Head (x)

d)     Tail (x)

e)      ProperSubstring (x)

f)       Subsequence (x)

2. Reduksilah state  DFA berikut ;
 

jawaban: 

1    1.Diketahui string (x) = aku , maka;

a)      ProperPrefix (x) = ak, a, ϵ

b)      Postfix (x) = aku, ku, u, ϵ

c)      Head (x) = a

d)     Tail (x) = u

e)      ProperSubstring (x) = ak, u, a, ku, k, ϵ

f)       Subsequence (x) = aku, ak, u, a, ku, k, au, ϵ

 2. a) state yang dihapus q2,

     b) pasangan state:

         (q0,q1),(q0,q3),(q0,q4),(q0,q5),(q0,q6),

         (q1,q3),(q1,q4),(q1,q5),(q1,q6),

         (q3,q4),(q3,q5),(q3,q6),

         (q4,q5),(q4,q6),

         (q5,q6).

     c) berikan predikat distinguishable(dapat dibedakan), jika pasangan state salah satunya adalah final state;

         (q0,q1)

         (q0,q3)

         (q0,q4)

         (q0,q5)

         (q0,q6) Distinguishable

         (q1,q3)

         (q1,q4)

         (q1,q5)

         (q1,q6) Distinguishable

         (q3,q4)

         (q3,q5)

         (q3,q6) Distinguishable

         (q4,q5)

         (q4,q6) Distinguishable

         (q5,q6) Distinguishable

     d) cari predikat pasangan state yang lainnya;

         (q0,q1)

          ᵟ(q0,a) = q1

          ᵟ(q1,a) = q5      

     ᵟ(q0,b) = q3

     ᵟ(q1,b) = q1 (indistinguishable)

         (q0,q3)

        
     ᵟ(q0,a) = q1

          ᵟ(q3,a) = q5       

     ᵟ(q0,b) = q3

     ᵟ(q3,b) = q1 (indistinguishable)

         (q0,q4)

          ᵟ(q0,a) = q1

          ᵟ(q4,a) = q4       

     ᵟ(q0,b) = q3

     ᵟ(q4,b) = q6 (distinguishable)

         (q0,q5)

         ᵟ(q0,a) = q1

          ᵟ(q5,a) = q4       

     ᵟ(q0,b) = q3

     ᵟ(q5,b) = q6 (distinguishable)     
          (q1,q3)

          ᵟ(q1,a) = q5

          ᵟ(q3,a) = q5       

     ᵟ(q1,b) = q1

     ᵟ(q3,b) = q1 (indistinguishable)

         (q1,q4)

          ᵟ(q1,a) = q5

          ᵟ(q4,a) = q4       

     ᵟ(q1,b) = q1

     ᵟ(q4,b) =  q6 (distinguishable)

         (q1,q5)

          ᵟ(q1,a) = q5

          ᵟ(q5,a) = q4      

     ᵟ(q1,b) = q1

     ᵟ(q5,b) = q6 (distinguishable)

         (q3,q4)

          ᵟ(q3,a) = q5

          ᵟ(q4,a) = q4       

     ᵟ(q3,b) = q1

     ᵟ(q4,b) = q6 (distinguishable)

         (q3,q5)

          ᵟ(q3,a) = q5

          ᵟ(q5,a) = q4       

     ᵟ(q3,b) = q1

     ᵟ(q5,b) = q6 (distinguishable)

         (q4,q5)

          ᵟ(q4,a) = q4

          ᵟ(q5,a) = q4       

     ᵟ(q4,b) = q6

     ᵟ(q5,b) = q6 (indistinguishable)

         dengan demikian;
         (q0,q1) Indistinguishable

         (q0,q3) Indistinguishable

         (q0,q4) Distingushable

         (q0,q5) Distingushable

         (q0,q6) Distingushable

         (q1,q3) Indistinguishable

         (q1,q4) Distingushable

         (q1,q5) Distingushable

         (q1,q6) Distingushable

         (q3,q4) Distingushable

         (q3,q5) Distingushable

         (q3,q6) Distingushable

         (q4,q5) Indistinguishable

         (q4,q6) Distingushable

         (q5,q6) Distingushable

     e)  kelompokan pasangan state yang indistinguishable yaitu (q0,q1), (q0,q3), (q1,q3)
          dan (q4,q5).
          dapat diartikan q0,q1,q3 saling indistingushable dan q4 indistinguishable dengan q5
     f)  DFA setelah direduksi sebagai berikut;