Properties

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 $(Q,\Sigma,E,S,F)$ with Q a finite set of states, $\Sigma$ a set of symbols, $S\subseteq Q$ the set of start states, $F\subseteq Q$ the set of final states and E a finite set of transitions $Q \times \Sigma \times Q$. Furthermore, let s(p,q) be the set of symbols on transitions from p to q, i.e., $s(p,q) = \{\sigma\vert(p,\sigma,q)\in E\}$. If M^c is such a (minimal) finite automaton then clearly the equivalent (minimal) pfsr is given by $(Q,\Sigma,2^\Sigma,E',S,F)$ where $E'=\{(p,s(p,q),q)\vert (p,s,q)\in E\}$. 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 $\vert\Sigma\vert$.