04TGS.P.4. Teori Bahasa Dan Otomata [PDF]

Citation preview

Teori Bahasa Dan Otomata Perteman ke-4



Nama : Bayu Tri Aji Nim



: 1844190002



Prodi



: TIF-S1



Essay 1. Buatlah NFA tanpa -move yang ekuivalen dengan NFA -move pada gambar di bawah ini , ( = {0,1,2})



0



q0







q1







Q = {q0,q1,q2}



Tabel transisi NFA ɛ-move



ɛ = {0,1,2} δ = q0 F = q2



2



1



δ' q0 q1 q2



0 q0 Ф Ф



δ’(q0,0)=  - closure (  ( - closure (q0), 0 )) =  - closure (  ( { q0, q1,q2 }, 0 )) =  - closure ( q0 )= { q0, q1,q2 } δ’(q0,1)=  - closure (  ( - closure (q0), 1 )) =  - closure (  ( { q0, q1,q2 }, 1 ))



1 Ф q1 Ф



2 Ф Ф q2







q2



ɛ-Clousen (q0) = {q0,q1,q2} ɛ-Clousen (q1) = {q1,q2} ɛ-Clousen (q2) = {q2}



=  - closure ( q1 )= {q1,q2 } δ’(q0,2)=  - closure (  ( - closure (q0), 2 )) =  - closure (  ( { q0, q1,q2 }, 2 )) =  - closure ( q2 )= {q2 } δ’(q1,0)=  - closure (  ( - closure (q1), 0 ))



=  - closure (  ( {q1,q2 }, 0 ))



=  - closure (  ( { q2 }, 0))



=  - closure (Ф )= { Ф }



=  - closure (Ф )= { Ф }



δ’(q1,1)=  - closure (  ( - closure (q1), 1 ))



δ’(q2,1) =  - closure (  ( - closure (q2), 1 ))



=  - closure (  ( {q1,q2 }, 1 ))



=  - closure (  ( { q2 }, 1))



=  - closure (q1 )= { q1,q2 }



=  - closure (Ф )= { Ф }



δ’(q1,2) =  - closure (  ( - closure (q1), 2 ))



δ’(q2,2)=  - closure (  ( - closure (q2), 0 ))



=  - closure (  ( {q1,q2 }, 2 ))



=  - closure (  ( { q2 }, 2))



=  - closure (q2 )= {q2}



=  - closure (q2 )= { q2 }



0



δ’(q2,0) =  - closure (  ( - closure (q2), 0 )) δ q0 q1 q2



0 1 q0,q1,q2 q1,q2 Ф q1,q2 Ф Ф  Tabel Transisi



1



2



0,1,2



2 q2 q2 q2



q0 0,1



q1 1,2



q2



°NFA tanpa ɛ-move



2. Buatlah NFA tanpa -move yang ekuivalen dengan NFA -move pada gambar di bawah ini , (∑ = {0,1,})



0



q0



q1







1 Q = {q0,q1}



F = q1



ɛ = {0,1}



δ' q0 q1



δ = q0



0 q0 Ф



1 Ф q1



Tabel transisi NFA ɛ-move



ɛ-Clousen (q0) = {q0,q1} ɛ-Clousen (q1) = {q1}



δ’(q0,0)=  - closure (  ( - closure (q0), 0 ))



δ’(q1,0)=  - closure (  ( - closure (q1), 0 ))



=  - closure (  ( { q0, q1 }, 0 ))



=  - closure (  ( {q1}, 0 ))



=  - closure ( q0 )= { q0, q1 }



=  - closure (Ф )= { Ф }



δ’(q0,1)=  - closure (  ( - closure (q0), 1 ))



δ’(q1,1)=  - closure (  ( - closure (q1), 1 ))



=  - closure (  ( { q0, q1 }, 1 ))



=  - closure (  ( {q1 }, 1 ))



=  - closure ( q1 )= {q0,q1 }



=  - closure (q1 )= { q0,q1 }



1



0 δ' 0 1 q0 q0,q1 q0,q1 q1 Ф q0,q1 Tabel transisi NFA ɛ-move



q0



0,1



1



Pilihan Ganda 1. NFA  – MOVE adalah mesin NFA yang diperbolehkan mengubah state tanpa …. a. membaca input



d. menerjemahkan input



b. mengecek output



e. memanipulasi output\



c. menghasilkan input



2. Dari gambar di atas, maka pernyataan yang benar adalah…. a. q0 tanpa membaca input dapat berpindah ke q1 b. q1 tanpa membaca input dapat berpindah ke q0 c. q4 tanpa membaca input dapat berpindah ke q3 d. q2 tanpa membaca input dapat berpindah ke q4 e. q1 tanpa membaca input dapat berpindah ke q3



q1



3. Himpunan state – state yang dapat dicapai dari suatu state tanpa membaca input disebut a. Deterministic Finite Automata



d. DFA  – MOVE



b.  - closure



e. Transisi



c. NFA  – MOVE



4. Dari gambar di atas, maka pernyataan yang salah adalah a.  - closure ( q0 ) = { q0, q1 } b.  - closure ( q2 ) = { q3 } c.  - closure ( q1 ) = { q1 } d.  - closure ( q2 ) = { q2 } e.  - closure ( q3 ) = { q3 }



5. Dari gambar di atas, maka pernyataan yang salah adalah a.  - closure ( q0 ) = { q0, q1, q2 } b.  - closure ( q1 ) = { q1, q2 } c.  - closure ( q2 ) = { q4 } d.  - closure ( q3 ) = { q3 } e.  - closure { q4 ) = { q1, q2, q4 }



6. Pada suatu state yang tidak memiliki transisi  maka  - closureny adalah a. output b. kebalikan dari state tersebut



d. state itu sendiri e. diagram transisi



c. himpunan kosong 7. Berikut ini yang bukan merupakan tahapan – tahapan / langkah ekivalensi NFA dengan  move ke NFA tanpa  - Move adalah… a. Membuat tabel Transisi NFA  - Move b. Tentukan  - Closure untuk setiap state c. Carilah setiap fungsi hasil perubahan dari NFA  - Move ke NFA tanpa  - Move dengan rumus : ’ ( state, input ) =  - closure (  ( - closure (state), input )) d. Buat tabel transisi & diagram transisi NFA tanpa  - Move yang ekivalensi dengan NFA  - Move  e. Membuat tabel transisi DFA ke NFA



NOTE : yang bergaris bawah dan bberwarna merah adalah jawaban.