Saya mencari contoh yang baik dari mesin negara yang terbatas; Bahasa tidak terlalu penting, hanya contoh yang bagus.

Implementasi kode berguna (pseudo-code umum), tetapi juga sangat berguna untuk mengumpulkan berbagai kegunaan FSM.

Contoh tidak harus berbasis komputer, misalnya contoh jaringan kereta api Mike Dunlavey, sangat berguna.

A Safe (acara dipicu)

• Negara : Beberapa "dikunci" negara, satu "membuka" negara
• Transisi : Kombinasi / kunci yang benar memindahkan Anda dari status terkunci awal ke status terkunci lebih dekat ke tidak terkunci, hingga akhirnya Anda bisa membuka kunci. Kombinasi / kunci yang salah membuat Anda kembali ke kondisi terkunci semula (terkadang dikenal sebagai idle .

Traffic Light (dipicu | sensor [event] terpicu)

• Negara : MERAH, KUNING, HIJAU (contoh paling sederhana)
• Transisi : Setelah pengatur waktu, ubah RED ke GREEN, GREEN ke YELLOW, dan YELLOW ke RED. Bisa juga dipicu merasakan mobil di berbagai negara (lebih rumit).

Mesin Penjual Otomatis (acara dipicu, variasi brankas )

• Negara : IDLE, 5_CENTS, 10_CENTS, 15_CENTS, 20_CENTS, 25_CENTS, dll, VEND, CHANGE
• Transisi : Sebutkan perubahan pada saat penyisipan koin, tagihan, transisi ke VEND pada jumlah pembelian yang benar (atau lebih), kemudian transisi ke CHANGE atau IDLE (tergantung seberapa etis Mesin Penjual Anda)

Contoh Protokol Gateway Perbatasan

BGP adalah protokol yang mendukung keputusan inti routing di internet. Ini memelihara tabel untuk menentukan jangkauan host dari node yang diberikan, dan membuat internet benar-benar terdesentralisasi.

Dalam jaringan, setiap node BGP adalah peer, dan menggunakan mesin keadaan terbatas, dengan salah satu dari enam status Idle , Connect , Active , OpenSent , OpenConfirm , dan Didirikan . Setiap koneksi peer dalam jaringan memelihara salah satu dari status ini.

Protokol BGP menentukan pesan yang dikirim ke rekan-rekan untuk mengubah statusnya.

Statistik BPG.

Diam

Status siaga pertama . Dalam keadaan ini, BGP menginisialisasi sumber daya, dan menolak upaya koneksi masuk, dan memulai koneksi ke peer.

Menghubungkan

Keadaan kedua Connect . Dalam keadaan ini, router menunggu koneksi selesai dan transisi ke status OpenSent jika berhasil. Jika tidak berhasil, ini akan me-reset timer ConnectRetry dan transisi ke status aktif setelah kedaluwarsa.

Aktif

Dalam keadaan aktif , router me-reset timer ConnectRetry ke nol dan kembali ke kondisi Connect .

OpenSent

Dalam keadaan OpenSent , router mengirim pesan Open dan menunggu balasannya. Pesan Keepalive dipertukarkan dan, setelah berhasil diterima, router ditempatkan ke dalam status Didirikan .

Mapan

Dalam kondisi mapan , router dapat mengirim / menerima: Keepalive; Memperbarui; dan Pesan pemberitahuan ke / dari rekannya.

Info lebih lanjut tentang BGP ada di wikipedia

Mereka berguna untuk memodelkan semua jenis hal. Misalnya, siklus pemilu dapat dimodelkan dengan negara di sepanjang garis (pemerintahan normal) - pemilihan yang disebut -> (kampanye awal) - Parlemen dibubarkan -> (kampanye berat) - pemilihan -> (penghitungan suara ). Kemudian baik (penghitungan suara) - tidak ada mayoritas -> (negosiasi koalisi) - kesepakatan tercapai -> (pemerintahan normal) atau (penghitungan suara) - mayoritas -> (pemerintahan normal). Saya telah mengimplementasikan varian pada skema ini dalam game dengan subtitle politik.

Mereka digunakan dalam aspek-aspek lain dari permainan juga: AI sering berbasis negara; transisi antara menu dan level, dan transisi setelah kematian atau level selesai sering dimodelkan dengan baik oleh FSM.

Parser CSV yang digunakan dalam plug-in jquery-csv

Ini adalah pengurai tata bahasa Chomsky Type III dasar .

Sebuah tokenizer regex digunakan untuk mengevaluasi data berdasarkan char-by-char. Ketika char kontrol ditemukan, kode dilewatkan ke pernyataan switch untuk evaluasi lebih lanjut berdasarkan keadaan awal. Karakter non-kontrol dikelompokkan dan disalin secara bersamaan untuk mengurangi jumlah operasi penyalinan string yang diperlukan.

Tokenizer:

var tokenizer = /("|,|\n|\r|[^",\r\n]+)/;

Set pertandingan pertama adalah karakter kontrol: pemisah nilai (") pemisah nilai (,) dan pemisah entri (semua variasi baris baru). Pertandingan terakhir menangani pengelompokan karakter non-kontrol.

Ada 10 aturan yang harus dipenuhi oleh parser:

• Aturan # 1 - Satu entri per baris, setiap baris diakhiri dengan baris baru
• Aturan # 2 - Mengejar baris baru di akhir file yang dihilangkan
• Aturan # 3 - Baris pertama berisi data tajuk
• Aturan # 4 - Spasi dianggap data dan entri tidak boleh mengandung tanda koma
• Aturan # 5 - Baris mungkin atau mungkin tidak dibatasi oleh tanda kutip ganda
• Aturan # 6 - Bidang yang berisi jeda baris, tanda kutip ganda, dan koma harus dilampirkan dalam tanda kutip ganda
• Aturan # 7 - Jika tanda kutip ganda digunakan untuk menyertakan bidang, maka tanda kutip ganda yang muncul di dalam bidang harus diloloskan dengan mendahului dengan tanda kutip ganda lainnya.
• Amandemen # 1 - Bidang yang tidak dikutip dapat atau mungkin
• Amandemen # 2 - Bidang yang dikutip mungkin atau tidak
• Amandemen # 3 - Bidang terakhir dalam entri mungkin mengandung nilai nol atau tidak

Catatan: 7 aturan teratas berasal langsung dari IETF RFC 4180 . 3 terakhir ditambahkan untuk menutupi kasus tepi yang diperkenalkan oleh aplikasi spreadsheet modern (ex Excel, Google Spreadsheet) yang tidak membatasi (yaitu kutipan) semua nilai secara default. Saya mencoba menyumbang kembali perubahan pada RFC tetapi belum mendengar tanggapan atas pertanyaan saya.

Cukup dengan wind-up, inilah diagram:

Menyatakan:

1. keadaan awal untuk entri dan / atau nilai
2. kutipan pembuka telah ditemukan
3. kutipan kedua telah ditemukan
4. nilai yang tidak dikutip telah ditemukan

Transisi:

• Sebuah. memeriksa kedua nilai yang dikutip (1), nilai yang tidak dikutip (3), nilai nol (0), entri nol (0), dan entri baru (0)
• b. memeriksa tanda kutip kedua (2)
• c. memeriksa kutipan yang lolos (1), nilai akhir (0), dan akhir entri (0)
• d. memeriksa nilai akhir (0), dan akhir entri (0)

Catatan: Sebenarnya tidak ada status. Harus ada garis dari 'c' -> 'b' yang ditandai dengan status '1' karena pembatas kedua yang lolos berarti pembatas pertama masih terbuka. Bahkan, mungkin akan lebih baik untuk menggambarkannya sebagai transisi lain. Menciptakan ini adalah seni, tidak ada cara yang benar.

Catatan: Ini juga kehilangan keadaan keluar tetapi pada data yang valid parser selalu berakhir pada transisi 'a' dan tidak ada negara yang mungkin karena tidak ada yang tersisa untuk diurai.

Perbedaan antara Negara dan Transisi:

Suatu negara terbatas, artinya hanya dapat disimpulkan sebagai satu hal.

Transisi mewakili aliran antar negara sehingga dapat berarti banyak hal.

Pada dasarnya, hubungan transisi state-> adalah 1 -> * (yaitu satu-ke-banyak). Negara mendefinisikan 'apa adanya' dan transisi mendefinisikan 'bagaimana penanganannya'.

Catatan: Jangan khawatir jika penerapan status / transisi tidak terasa intuitif, itu tidak intuitif. Butuh korespondensi yang luas dengan seseorang yang jauh lebih pintar daripada saya sebelum akhirnya saya memiliki konsep untuk bertahan.

Pseudo-Code:

csv = // csv input string

// init all state & data
state = 0
value = ""
entry = []
output = []

endOfValue() {
  entry.push(value)
  value = ""
}

endOfEntry() {
  endOfValue()
  output.push(entry)
  entry = []
}

tokenizer = /("|,|\n|\r|[^",\r\n]+)/gm

// using the match extension of string.replace. string.exec can also be used in a similar manner
csv.replace(tokenizer, function (match) {
  switch(state) {
    case 0:
      if(opening delimiter)
        state = 1
        break
      if(new-line)
        endOfEntry()
        state = 0
        break
      if(un-delimited data)
        value += match
        state = 3
        break
    case 1:
      if(second delimiter encountered)
        state = 2
        break
      if(non-control char data)
        value += match
        state = 1
        break
    case 2:
      if(escaped delimiter)
        state = 1
        break
      if(separator)
        endOfValue()
        state = 0
        break
      if(newline)
        endOfEntry()
        state = 0
        break
    case 3:
      if(separator)
        endOfValue()
        state = 0
        break
      if(newline)
        endOfEntry()
        state = 0
        break
  }
}

Catatan: Ini intinya, dalam praktiknya ada banyak lagi yang perlu dipertimbangkan. Misalnya, pengecekan kesalahan, nilai null, garis akhir kosong (yaitu yang valid), dll.

Dalam hal ini, negara adalah kondisi ketika blok pencocokan regex menyelesaikan iterasi. Transisi direpresentasikan sebagai pernyataan kasus.

Sebagai manusia, kita memiliki kecenderungan untuk menyederhanakan operasi tingkat rendah ke tingkat yang lebih tinggi abstrak tetapi bekerja dengan FSM yang bekerja dengan operasi tingkat rendah. Sementara negara dan transisi sangat mudah untuk dikerjakan secara individual, secara inheren sulit untuk memvisualisasikan semuanya sekaligus. Saya merasa paling mudah untuk mengikuti jalur eksekusi individu berulang-ulang sampai saya bisa melihat bagaimana transisi berlangsung. Ini seperti belajar matematika dasar, Anda tidak akan dapat mengevaluasi kode dari tingkat yang lebih tinggi sampai detail tingkat rendah mulai menjadi otomatis.

Selain: Jika Anda melihat implementasi yang sebenarnya, ada banyak detail yang hilang. Pertama, semua jalur yang mustahil akan menghasilkan pengecualian khusus. Seharusnya tidak mungkin mengenai mereka, tetapi jika ada kerusakan mereka akan benar-benar memicu pengecualian pada pelari uji. Kedua, aturan parser untuk apa yang diizinkan dalam string data CSV 'legal' cukup longgar sehingga kode yang diperlukan untuk menangani banyak kasus tepi tertentu. Terlepas dari fakta itu, ini adalah proses yang digunakan untuk mengejek FSM sebelum semua perbaikan bug, ekstensi, dan fine tuning.

Seperti kebanyakan desain, itu bukan representasi yang tepat dari implementasi tetapi menguraikan bagian-bagian penting. Dalam praktiknya, sebenarnya ada 3 fungsi parser berbeda yang berasal dari desain ini: pemisah garis csv-spesifik, parser garis tunggal, dan parser multi-garis lengkap. Mereka semua beroperasi dengan cara yang sama, mereka berbeda dalam cara mereka menangani karakter baris baru.

FSM sederhana di Jawa

int i=0;

while (i<5) {
 switch(i) {
   case 0:
     System.out.println("State 0");
     i=1;
     break;
   case 1:
     System.out.println("State 1");
     i=6;
     break;
   default:
     System.out.println("Error - should not get here");
     break;      
  }

} 

Ini dia. OK, itu tidak brilian, tapi itu menunjukkan ide.

Anda akan sering menemukan FSM dalam produk telekomunikasi karena mereka menawarkan solusi sederhana untuk situasi yang rumit.

Saya telah menemukan bahwa memikirkan / memodelkan lift (lift) adalah contoh yang baik dari mesin keadaan terbatas. Ini membutuhkan sedikit cara pengenalan, tetapi menyediakan jauh dari situasi sepele untuk diimplementasikan.

Negara-negara bagian, misalnya, di lantai dasar, di lantai pertama, dll, dan memindahkan tanah ke lantai satu, atau memindahkan lantai tiga ke lantai tetapi saat ini antara lantai 3 dan 2, dan seterusnya.

Efek tombol di sangkar lift dan di lantai itu sendiri memberikan input, efek yang tergantung pada kedua tombol yang ditekan bersama dengan keadaan saat ini.

Setiap lantai, kecuali bagian atas dan bawah, akan memiliki dua tombol: satu untuk meminta lift untuk naik, yang lain untuk turun.

OKE, ini sebuah contoh. Misalkan Anda ingin menguraikan integer. Ini akan pergi seperti di dd*mana ddigit bilangan bulat.

state0:
    if (!isdigit(*p)) goto error;
    p++;
    goto state1;
state1:
    if (!isdigit(*p)) goto success;
    p++;
    goto state1;

Tentu saja, seperti yang dikatakan @Gary, Anda dapat menyamarkannya gotomelalui pernyataan peralihan dan variabel status. Perhatikan bahwa dapat disusun untuk kode ini, yang isomorfik dengan ekspresi reguler asli:

if (isdigit(*p)){
    p++;
    while(isdigit(*p)){
        p++;
    }
    // success
}
else {
    // error
}

Tentu saja Anda juga bisa melakukannya dengan tabel pencarian.

Mesin negara yang terbatas dapat dibuat dengan berbagai cara, dan banyak hal dapat digambarkan sebagai mesin negara yang terbatas. Ini bukan "benda", melainkan konsep, untuk memikirkan berbagai hal.

Contoh Jaringan Kereta Api

Salah satu contoh FSM adalah jaringan kereta api.

Ada sejumlah saklar yang terbatas di mana kereta api bisa menuju salah satu dari dua jalur.

Ada sejumlah terbatas trek yang menghubungkan sakelar-sakelar ini.

Kapan saja, sebuah kereta ada di satu lintasan, ia dapat dikirim ke lintasan lain dengan melewati sakelar, berdasarkan pada sedikit informasi input.

Mesin Hingga Hingga di Ruby:

module Dec_Acts
 def do_next
    @now = @next
    case @now
    when :invite
      choose_round_partner
      @next = :wait
    when :listen
      @next = :respond
    when :respond
      evaluate_invites
      @next = :update_in
    when :wait
      @next = :update_out
    when :update_in, :update_out
      update_edges
      clear_invites
      @next = :exchange
    when :exchange
      update_colors
      clear_invites
      @next = :choose
    when :choose
      reset_variables
      choose_role
    when :done
      @next = :done
    end
  end
end

Itulah perilaku node komputasi tunggal dalam sistem terdistribusi, menyiapkan skema komunikasi berbasis tautan. Lebih atau kurang. Dalam bentuk Grafik terlihat seperti ini:

Lihatlah tautan ini untuk beberapa contoh sederhana analisis leksikal (FSM):

http://ironbark.bendigo.latrobe.edu.au/subjects/SS/clect/clect03.html

Anda juga dapat melihat "buku naga" sebagai contoh (bukan bacaan ringan)

http://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools

Dalam praktiknya, Mesin Negara sering digunakan untuk:

• Tujuan desain (memodelkan berbagai tindakan dalam suatu program)
• Pengurai bahasa alami (tata bahasa)
• Penguraian string

Salah satu contoh akan menjadi Mesin Negara yang memindai string untuk melihat apakah ia memiliki sintaks yang tepat. Kode ZIP Belanda misalnya diformat sebagai "1234 AB". Bagian pertama hanya berisi angka, huruf kedua saja. Mesin Negara dapat ditulis yang melacak apakah itu dalam keadaan NUMBER atau dalam kondisi SURAT dan jika menemukan input yang salah, tolaklah.

Mesin negara akseptor ini memiliki dua status: numerik dan alfa. Mesin keadaan dimulai dalam keadaan angka, dan mulai membaca karakter string untuk memeriksa. Jika karakter yang tidak valid ditemukan selama salah satu negara bagian, fungsi kembali dengan nilai False, menolak input sebagai tidak valid.

Kode python:

import string

STATE_NUMERIC = 1
STATE_ALPHA = 2

CHAR_SPACE = " "

def validate_zipcode(s):
cur_state = STATE_NUMERIC

for char in s:
    if cur_state == STATE_NUMERIC:
        if char == CHAR_SPACE:
            cur_state = STATE_ALPHA
        elif char not in string.digits:
            return False
    elif cur_state == STATE_ALPHA:
        if char not in string.letters:
            return False
return True

zipcodes = [
    "3900 AB",
    "45D6 9A",
]

for zipcode in zipcodes:
    print zipcode, validate_zipcode(zipcode)

Sumber: (Hingga-) Mesin Negara dalam praktik