Timely fault detection due to natural (cosmic rays) or targeted (electromagnetic pulse) effects is a serious problem in developing fault-tolerant and reliable finite state machines (FSMs). Since finite automata often serve as control devices (controllers), it is also important to prevent a fault from negatively affecting the controlled object. The paper presents the technique for constructing structural models of fault-tolerant Moore FSMs when ones are realized in field programmable gate arrays (FPGAs). The proposed approach does not degrade the performance of FSMs and differs from known methods for designing fault-tolerant FSMs with very small overheads. Examples of practical use of the presented technique are given. The Conclusion highlights promising directions for future research.