Abstract: A general model of finite state machines which contains gates and memory elements subject to soft failures has been proposed and a computational method for determining probability of state transition errors is provided. A new type of fault-tolerant finite state machine using error correcting codes and "cluster state" is presented. Probability of transition errors has bee computed and a comparison with general realization has been made. It reveals that this kind of machines has inherent noise immunity for state transition.