OTOMATA HINGGA NONDETERMINISTIK

Seperti yang sudah di bahas di materi sebelumnya,  otomata dibagi menjadi dua jenis, Deterministik (AHD) dan Nondeterministik (AHN). Dan jika dilihat dari isi tabelnya, jelas terlihat perbedaan dari AHD dan AHN. Berikut datailnya :

Otomata Hingga Deterministik (AHD)
Fungsi Transisi akibat pembacaan sebuah simbol bersifat tertentu, artinya 
- Setiap cell hanya terdapat satu (1) digit stata tujuan
- Setiap stata terdapat busur panah keluar sebanyak input yang ada

Otomata Hingga Nondeterministik (AHN)

Fungsi Transisi akibat pembacaan sebuah simbol bersifat tertentu, artinya
- Setiap cell dapat berisi nol, satu bahkan lebih dari satu digit
- Setiap stata boleh terdapat busur panah dengan input yang sama, namun tujuan yang berbeda.


EQUIVALENSI AHN MENJADI AHD

Bentuk Otomata Nondeterministik dapat diubah menjadi bentuk Deterministik tanpa mengubah arti.
Berikut Algoritmanya :
1. Tetapkan Stata awal AHD = Stata awal AHN atau selanjutnya ditulis S(AHD) = S(AHN)
2. Tetapkan Input AHD = Input AHN atau selanjutnya ditulis V(AHD) = V(AHN)
3. Copykan tabel AHN sebagai tabel AHD, mula-mula Stata AHD = Stata AHN atau selanjutnya ditulis K(AHD) = K(AHN) dan Fungsi transisi AHD = Fungsi transisi AHN atau selanjutnya ditulis M(AHD) = M(AHN)
4. Setiap stata yang merupakan nilai dari fungsi M(AHN) namun stata tersebut bukan elemen dari K(AHN), maka tetapkanlah sebagai elemen baru dari K(AHD). Tempatkan stata tersebut pada kolom stata M(AHD). Lakukan pemetaan sesuai berdasarkan fungsi M(AHN).
5. Ulangi langkah 4 hingga tidak diperoleh stata baru.
6. Stata Penerima AHD atau selanjutnya ditulis Z(AHD) adalah semua stata yang mengandung stata elemen Z(AHN).

Contoh Soal :
Buatlah AHD yang equivalen dengan AHN berikut : 

Jawab :

1. S(AHN) = S(AHD) = A

2. V(AHN) = V(AHD) = {0,1}

3. Copykan tabel AHN

4. Simbol - dianggap sebagai elemen baru, kemudian petakan berdasarkan fungsi M(AHN).
5 karena tidak ada pengulangan makan lanjutkan ke langkah berikutnya.
6. Z(AHD) = Z(AHN) = {B} karena tidak ada lagi elemen baru yang mengandung elemen Z(AHN).

dan hasilnya adalah :