NFA with ^ move

AHN with ^ atau biasa ditulis AHN-^ merupakan jenis otomata baru, artinya otomata ini dapat berpindah stata tanpa membaca input.

Seperti pada gambar mesin otomata di atas, stata q0 tanpa membaca input dapat berpindah ke stata q1, begitu pula q1. Stata q1 tanpa membaca input dapat berpindah ke q2.

Seperti yang sudah dijelaskan, bahwa AHN-^ dapat dibuat AHN yang ekivalen, dengan demikian dapat pula dibuat AHD yang ekivalen.

Untuk mengubah AHN-^ yang ekivalen dengan AHN, harus mencari nilai ^- Closure setiap stata. Apakah ^- Closure(stata) itu?

^- Closure suatu stata atau biasa ditulis ^- Cl(stata) adalah himpunan stata-stata yang dapat dicapai dari suatu stata tanpa membaca input.

Dari gambar mesin otomata di atas dapat diperoleh :
^- Cl(q0) = {q0, q1}
^- Cl(q1) = {q1, q2}
^- Cl(q2) = {q2}

EQUIVALENSI AHN-ε ke AHN

Untuk memudahkan kita mencari ekivalensi AHN dari AHN-^, gunakanlah Algoritma atau langkah-langkah sebagai berikut :

1. Tentukan ^ - closurenya
2. Buat tabel transisi AHN-^
3. Carilah setiap fungsi transisi hasil perubahan dari AHN-^ ke AHN dengan rumus berikut: M(Stata,Input) = ^-Cl (M(^-Cl(Stata),input) )
4. Berdasarkan hasil no 3, buatlah tabel transisi dan diagram transisinya
5. Stata penerimanya Z(AHN) adalah : stata penerima pada AHN-^ ditambah stata pada^-Cl yang hasilnya mengandung stata penerima pada AHN-^