Finite State Automata

Contoh :

seorang petani dengan seekor serigala, kambing dan seikat rumput berada pada suatu sisi sungai. Tersedia hanya sebuah perahu kecil yang hanya dapat dimuati dengan petani tersebut dengan salah satu serigala, kambing atau rumput. Petani tersebut harus menyeberangkan ketiga bawaannya kesisi lain sungai. Tetapi jika petani meninggalkan serigala dan kambing pada suatu saat, maka kambing akan dimakan serigala. Begitu pula jika kambing ditinggalkan dengan rumput, maka rumput akan dimakan oleh kambing. Mungkinkah ditemukan suatu cara untuk melintasi sungai tanpa menyebabkan kambing atau rumput dimakan. 

 

16 kemungkinan kombinasi state

Sisi kiri	Sisi Kanan	Simbol State
PSKR	Ø	PSKR – Ø
SR	PK	SR – PK
SK	PR	SK – PR
KR	PS	KR – PS
PSR	K	PSR – K
PSK	R	PSK – R
PKR	S	PKR – S
PK	SR	PK – SR
PR	SK	PR – SK
PS	KR	PS – KR
K	PSR	K – PSR
R	PSK	R – PSK
S	PKR	S – PKR
SKR	P	SKR – P
P	SKR	P – SKR
Ø	PSKR	Ø – PSKR

  

Dari 16 kemungkinan kombinasi state , hanya 10 state yang memenuhi syarat

 

Sisi kiri	Sisi Kanan	Simbol State
PSKR	Ø	PSKR – Ø
SR	PK	SR – PK
PSR	K	PSR – K
PSK	R	PSK – R
PKR	S	PKR – S
PK	SR	PK – SR
K	PSR	K – PSR
R	PSK	R – PSK
S	PKR	S – PKR
Ø	PSKR	Ø – PSKR

Berdasarkan kemungkinan state tersebut, dapat digambarkan diagram transisi dari persoalan tersebut dengan mesin automata, sbb:

 

Pada diagram diatas, arti bentuk-bentuk adalah sebagai berikut :

• lingkaran merepresentasikan kedudukan (state)
• label pada lingkaran adalah nama state tersebut
• busur menyatakan transisi
• label pada busur adalah masukan/input
• lingkaran didahului dengan sebuah busur tanpa label adalah state awal
• limgkaran ganda menyatakan state akhir(finish)

Algoritma Permainan Logika serigala, kambing dan rumput yang diseberangkan oleh petani
1. Mulai
2. Terdapat 3 objek yang akan diseberangkan oleh petani
3. Petani berangkat sendiri , misi gagal karena rumput dimakan kambing dan kambing dimakan serigala
4. Rumput dan Petani berangkat, misi gagal karena kambing dimakan serigala.
5. Serigala dan Petani berangkat, misi gagal karena rumput dimakan kambing.
6. Kambing dan Petani berangkat, petani kembali sendiri
7. Petani dan rumput berangkat.
8. Jika petani kembali sendiri, maka misi gagal karena rumput dimakan kambing, dan
9. Jika petani dan kambing kembali, maka lanjutkan langkah 10
10. Jika petani berangkat sendiri, maka misi gagal karena kambing dimakan serigala, dan
11. Jika Petani dan serigala berangkat, maka lanjutkan langkah 12
12. Petani kembali sendiri, petani dan kambing berangkat
13. Misi sukses
14. Selesai.