Identity

The identity relation for a given language L is $id(L)=\{(w,w) \vert w\in L\}$. For a given pfsr $M=(Q,\Sigma,\Pi,E,S,F)$, the identity relation is given by the pfst $M'=(Q,\Sigma,\Pi,E',S,F)$. Note that it would be wrong to define $E' = \{(p,\pi,\pi,q,0)\vert(p,\pi,q)\in E\}$. Suppose $\pi$ is true only of $\sigma_1,\sigma_2$. The pair $\pi:\pi$ then would be true of the pairs of symbols $\{(\sigma_1,\sigma_1), (\sigma_1,\sigma_2), (\sigma_2,\sigma_1), (\sigma_2,\sigma_2)\}$, whereas identity requires that we only allow the pairs $\{(\sigma_1,\sigma_1),(\sigma_2,\sigma_2)\}$. Another example to stress the point: the expression identity(?) (`copy') is quite different from ?:? (`garbage-in garbage-out'). It is therefore necessary to introduce an identity marker for each of the transitions. The identity of a pfsr $M=(Q,\Sigma,\Pi,E,S,F)$ is given by $id(M) = (Q,\Sigma,\Pi,E',S,F)$ where $E' = \{(p,\pi,\pi,q,1)\vert (p,\pi,q) \in E\}$.

The operations domain, range and inverse are straightforward. For a given pfst $M=(Q,\Sigma,\Pi,E,S,F)$, we have:

• domain(R(M)) is given by the pfsr $M'=(Q,\Sigma,\Pi,E',S,F)$ where $E' = \{(p,\phi,q)\vert(p,\phi,\psi,q,i)\in E\}$.

• range(R(M)) is given by the pfsr $M'=(Q,\Sigma,\Pi,E',S,F)$ where $E' = \{(p,\psi,q)\vert(p,\phi,\psi,q,i)\in E\}$.

• inverse(R(M)) is given by the pfst $M'=(Q,\Sigma,\Pi,E',S,F)$ where $E' = \{(p,\psi,\phi,q,i)\vert(p,\phi,\psi,q,i)\in E\}$.