NFA dengan Ɛ-Move

Materi Senin, 30 Mei 2016

NFA dengan Ɛ-move mempunyai jenis otomata baru (Ɛ disini bisa dianggap sebagai empty). Pada NFA dengan Ɛ-move (transisi Ɛ), diperbolehkan merubah state tanpa membaca input. Disebut dengan transisi Ɛ karena tidak bergantung pada suatu input ketika melakukan transisi.

 

Ekuivalensi Antar Deterministic Finite Automata (Reduksi)

Ekuivalensi dari NFA ke DFA
- NFA  = Dapat menghasilkan output lebih dari 1
- DFA = Hanya menghasilkan output 1

Menentukan Distinguable dan Indistinguable State Graph

Perbaikan :
Lakukan reduksi jumlah state pada Deterministic Finite Automata berikut :

Contoh 2 :

Step Game Logika Cross The River (Menyeberangi Sungai)

Nih game lumayan sulit buat yang jarang mikir karena bermain logika, betul-betul ngasah otak
Mari Kita Mencoba... Cemunguuuuddd ^,^ 

Inti dari permainan logika ini adalah menyeberangkan seluruh orang yang ada digame, yaitu terdiri dari :
1. Seorang Ayah + 2 Anak Laki-lakinya
2. Seorang Ibu + 2 Anak Perempuannya
3. Seorang Polisi + Penjahat
 

Peraturan :
- Sebrangkan mereka secara damai
- Perahu hanya bisa membawa 2 orang dan harus orang dewasa salah satunya (Ibu/Ayah/Polisi)
- Perahu juga boleh mondar-mandir dan tidak ada batasan waktu
- Orang dewasa (Ibu/Ayah/Polisi) boleh menaiki perahu secara bersamaan
- Jika anak laki-laki di tinggal oleh Ayah, dia akan dibunuh Ibu
- Jika anak perempuan di tinggal Ibu, dia akan dibunuh Ayah
- Dan jangan tingalkan anak dengan penjahat, mereka pasti dibantai.

Step-step Permainan Menyebrangi Sungai menggunakan Rakit :
1. Polisi dengan Penjahat menyebrangi sungai terlebih dahulu, Penjahat turun
 

2. Polisi kembali
 

3. Polisi dengan 1 Anak Laki-laki menyebrangi sungai, Anak Laki-laki turun
 

4. Polisi kembali dengan Penjahat
 

5. Ayah dengan Anak Laki-laki menyebrangi sungai, Anak Laki-laki turun
 

6. Ayah kembali
 

7. Ayah dengan Ibu menyebrangi sungai, Ayah turun
 

8. Ibu kembali
 

9. Kemudian Polisi dengan Penjahat menyebrangi sungai lagi, Polisi dan Penjahat turun
 

10. Akan tetapi, Ayah kembali menjemput Ibu
 

11. Ayah dan Ibu menyebrangi sungai, Ayah turun
 

12. Ibu kembali untuk menjemput Anaknya
 

13. Ibu dengan 1 Anak Perempuan, Ibu dan Anak Perempuan turun
 

14. Lalu Polisi dengan Penjahat kembali
 

15. Polisi dengan Anak Perempuan yang lain menyebrangi sungai, Anak Perempuan turun
 

16. Polisi kembali untuk menjemput Penjahat
 

17. Polisi dan Penjahat kembali menyebrangi sungai
 

18. Final State, semua bahagia karena mereka dapat menyeberangi sungai dengan aman dan selamat
 
Jadi di game ini, hanya polisilah yang baik.

Ket :
P1P2 = Polisi - Penjahat
P1 = Polisi
P1An1 = Polisi - Anak Laki-laki 1
A An2 = Ayah - Anak Laki-laki 2
A = Ayah
A I = Ayah - Ibu
I = Ibu
I AP1 = Ibu  - Anak Perempuan 1
P1 AP2 = Polisi - Anak Perempuan 2

Grammar dan Bahasa

Assalamualaikum.wr.wb..

Kali ini saya mendapat tugas untuk Menentukan Grammar Sebuah Bahasa. Alhamdulillah saya dapat menyelesaikannya dengan tepat waktu. Maka dari itu mari kita bahas.. :)

• Grammar Reguler

 

• Grammar Bebas Konteks

  

• Grammar Konteks Sensitive

• Grammar Unrestricted

Hirarki Chomsky

Assalamualaikum.wr.wb :)
Blog ini saya buat sebagai tugas dari salah satu dosen saya. Disini saya akan membahas tentang "HIRARKI CHOMSKY".
Selamat membaca :)

--Hirarki Chomsky--
Hirarki Chomsky mempunyai 4 class tingkatan, yaitu :
1. Tipe 0 (Unrestricted)
Pada tipe 0 ini "simbol  ruas sebelah kiri harus minimal ada sebuah simbol variabel dan tidak ada batasan pada aturan produksi". Tipe 0 menggunakan mesin automata dengan Mesin Turing.

2. Tipe 1 (Context Sensitive)
Pada tipe 1 ini "simbol pada ruas sebelah kiri harus minimal ada sebuah variabel dan panjang String ruas kiri harus lebih kecil atau sama dengan ruas kanan (|a| <=|B|)". Tipe 1 menggunakan mesin automata dengan Linier Bounded Automata. 

3. Tipe 2 (Context Free / Bebas Konteks)
Pada tipe 2 ini "simbol sebelah kiri harus simbol variabel". Tipe 2 menggunakan mesin automata dengan Push Down Automata.

4. Tipe 3 (Regular)
Pada tipe 3 ini "simbol sebelah kiri harus berupa simbol variabel dan simbol sebelah kanan maksimal hanya memiliki sebuah simbol variabel dan bila ada terletak di paling kanan". Tipe 3 menggunakan mesin automata dengan Finite State Automata DFA dan NFA.