We propose a non-intrusive methodology for concurrent fault detection in FSMs. The proposed method is similar to duplication, wherein a replica of the circuit acts as a predictor that immediately detects potential faults by comparison to the original FSM. However, instead of duplicating the FSM, the proposed method selects a few prediction functions which only partially replicate it. Selection is guided by the objective of minimizing the incurred hardware overhead without compromising the ability to detect all faults, yet possibly introducing fault detection latency. Furthermore, in contrast to concurrent error detection approaches which presume the ability to re-synthesize the FSM and exploit parity-based state encoding, the proposed method does not interfere with the encoding and implementation of the original FSM. Experimental results indicate that the proposed method achieves significant hardware overhead reduction over duplication, while detecting more than 99% of all permanent faults with very low average fault detection latency.