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;

          

Opening

Operasi Morfologi Opening

Operasi morfologi opening merupakan operasi erosi yang diikuti dengan dilasi dimana digunakan SE yang sama. Operasi opening akan menghilangkan seluruh piksel di area yang terlalu kecil untuk ditempati oleh SE dan menghaluskan kontur objek. Operasi opening A dengan strel B dengan notasi A○B yaitu seperti pada persamaan:

                                                        A B = (A⊖B)⊕B

Contoh opening:

Langkah pertama adalah erosi;

A         = {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}

B         = {(0,0),(0,1),(1,0)}

A⊖B  = {(1,1),(1,2),(2,1),(2,2)}       

Langkah kedua adalah dilasi;

A⊖B              = {(1,1),(1,2),(2,1),(2,2),(4,4)}    

B                     = {(0,0),(0,1),(1,0)}

(A⊖B)⊕B     = {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2)}

Gambar  Opening A dengan B

referensi;

1. Gonzalez, R.C. dan Woods, R.E., 2008, Digital Image processing, Addison- Wesley Publishing Company, USA.
2. Pujiastuti, A., 2016, Sistem Perhitungan Lama Penyinaran Matahari Dengan Metode Otsu Threshold (Studi kasus: St. Klimatologi Barongan), Tesis, Program Studi S2 Ilmu Komputer Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Gadjah Mada Yogyakarta
3. Putra, D.,2010, Pengolahan Citra Digital, Andi Yogyakarta, Yogyakarta