Intersection

An important and powerful operation is intersection. In the classical case, an automaton for the intersection of the languages defined by two given automata M₁ and M₂ is constructed by considering the cross product of states of M₁ and M₂. A transition $((p_1,p_2),\sigma,(q_1,q_2))$ exists iff the corresponding transition $(p_1,\sigma,q_1)$ exists in M₁ and $(p_2,\sigma,q_2)$ exists in M₂. In the case of pfsr a similar construction can be used, but instead of requiring that the symbol $\sigma$ occurs in the corresponding transitions of M₁ and M₂, we require that the resulting predicate is the conjunction of the corresponding predicates in M₁ and M₂. The same technique is described in [35].

Given $\epsilon$-free pfsr $M_1=(Q_1,\Sigma,\Pi,E_1,S_1,F_1)$ and $M_2=(Q_2,\Sigma,\Pi,E_2,S_2,F_2)$, the intersection $L(M_1) \cap L(M_2)$ is the language accepted by $M=(Q_1 \times Q_2,\Sigma,\Pi,E,S_1\times S_2, F_1\times F_2)$ and $E=\{((p_1,q_1),\pi_1\wedge\pi_2,(p,q))\vert (p_1,\pi_1,p)\in E_1, (q_1,\pi_2,q)\in E_2\}$.