We discuss a non-intrusive methodology for concurrent error detection in FSMs. The proposed method is based on compaction and monitoring of the state/output bits of an FSM via parity trees. While errors may affect more than one state/output bit, not all combinations of state/output bits constitute potential erroneous cases for a given fault model. Therefore, it is possible to compact them without loss of error information. Thus, concurrent error detection is performed through hardware that predicts the values of the compacted state/output bits and compares them to the actual values of the FSM. In order to minimize the incurred hardware overhead, a randomized algorithm is proposed for selecting the minimum number of required parity functions.