Jelaskan Model Matematika dari Mesin finite-state

Sesuai dengan klasifikasi umum, definisi formal berikut ditemukan.

FSM  deterministik atau akseptor FSM deterministik adalah kuintupel , di mana:

adalah yang digunakan sebagai alfabet masukan (himpunan simbol berhingga yang tidak kosong);

adalah yang digunakan sebagai alfabet himpunan status tak-kosong berhingga;

adalah yang digunakan sebagai alfabet state awal, elemen dari ;

adalah yang digunakan sebagai alfabet fungsi transisi-state:  :  (dalam robot berhingga non deterministik itu akan menjadi , i.e.  akan mengembalikan satu set status);

adalah yang digunakan sebagai alfabet himpunan state akhir, himpunan bagian (mungkin kosong) dari .

Untuk FSM deterministik dan non-deterministik, penggunaan  adalah fungsi parsial, yaitu <math>\delta(s, x)</math> tidak harus ditentukan untuk setiap kombinasi dari  dan . Jika FSM  dalam keadaan , simbol berikutnya adalah  dan  tidak ditentukan, maka  dapat mengumumkan kesalahan tersebut yaitu menolak input. Ini berguna dalam definisi mesin state umum, tetapi kurang berguna saat mengubah mesin. Beberapa algoritma dalam bentuk defaultnya mungkin memerlukan fungsi total.

FSM memiliki daya komputasi yang sama dengan mesin Turing yang dibatasi sedemikian rupa sehingga kepalanya hanya dapat melakukan operasi "baca", dan harus selalu bergerak dari kiri ke kanan. Artinya, setiap bahasa formal yang diterima oleh FSM diterima oleh jenis mesin Turing yang dibatasi, dan sebaliknya.

Transduser FSM adalah sextuple , dimana:

adalah yang digunakan sebagai alfabet masukan (himpunan simbol berhingga yang tidak kosong);

adalah yang digunakan sebagai alfabet keluaran (kumpulan simbol tak kosong yang terbatas);

adalah yang digunakan sebagai himpunan status tak-kosong berhingga;

adalah yang digunakan sebagai state awal, elemen dari ;

adalah yang digunakan sebagai fungsi transisi-keadaan: ;

adalah yang digunakan sebagai fungsi keluaran.

Jika fungsi keluaran bergantung dari status dan simbol masukan () definisi tersebut sesuai dengan model Mealy, dan jika dapat dimodelkan sebagai mesin Mealy. Jika fungsi dari keluaran hanya bergantung pada keadaan () definisi tersebut sesuai dengan model Moore, dan dapat dimodelkan sebagai mesin Moore. FSM tanpa fungsi keluaran sama sekali dikenal sebagai semi-otomatis atau sistem sistem transisi.

Jika kita mengabaikan simbol dari keluaran pertama mesin Moore, , maka dari itu simbol tersebut dapat dengan mudah diubah menjadi mesin Mealy yang setara dengan keluaran dengan mengatur fungsi keluaran dari setiap transisi  yang Mealy (yaitu memberi label setiap tepi) dengan simbol keluaran yang diberikan dari negara tujuan Moore. Transformasi sebaliknya kurang mudah karena status mesin Mealy mungkin memiliki label keluaran yang berbeda pada transisi masuknya (tepi). Setiap status tersebut perlu dibagi dalam beberapa status mesin Moore, satu untuk setiap simbol keluaran insiden.