It is clear that in the case of recognizers, the addition of predicates
is of limited theoretical interest. Let *M*^{c} be a classical finite
automaton
with *Q* a finite set of states,
a set of symbols, the set of start states, the set of final states and *E* a finite set of transitions
. Furthermore, let *s*(*p*,*q*) be the set of
symbols on transitions from *p* to *q*, i.e.,
. If *M*^{c} is such a (minimal) finite
automaton then clearly the equivalent (minimal) pfsr is given by
where
. The construction in the other direction is similar.

The pfsr device typically is more compact in the number of transitions than an equivalent finite automaton. In the worst case, however, the number of transitions is the same (if it is the case for all states that its outgoing transitions have different target states for each symbol). In the best case, the number of transitions is reduced by a factor of .