Teori Bahasa dan Otomata

Berikut adalah skema dan tabel kemungkinan kombinasi state dari permainan 8 orang menyeberangi sungai. 

Di dalam permainan tersebut terdapat 8 orang yaitu : 

1. Polisi (P)
2. Maling (M)
3. Ayah (A)
4. Anak ayah1 (A1)
5. Anak ayah2 (A2)
6. Ibu (I)
7. Anak ibu1 (I1)
8. Anak ibu2 (I2)

Peraturan :

• 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 dipukuli Ibu
• Jika anak perempuan di tinggal Ibu, dia akan dipukuli Ayah
• Dan jangan tingalkan anak dengan Maling, mereka pasti dipukuli. 

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

2. Polisi kembali
 

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

4. Polisi kembali dengan Maling
 

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 Maling menyebrangi sungai lagi, Polisi dan Maling 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 Maling kembali
 

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

16. Polisi kembali untuk menjemput Maling
 

17. Polisi dan Maling kembali menyebrangi sungai
 

18. Final State, semua bahagia karena mereka dapat menyeberangi sungai dengan aman dan selamat