Theorem 1. For a PSST T and NFA A, the post-image $$R (L)$$, where L is the regular language accepted by A, and R is the relation (actually function) defined by T, is not guaranteed to be regular.

Proof. We just give a trivial example:

Suppose $$L = L (A) = L (a^{\ast})$$, T contains only the initial and accepting state $$q_0$$. and three string variables X, Y, and Z. The only transition is $$(q_0, a, q_0, s)$$, where $$s (X) = Xa, s (Y) = Yb, s (Z) = Zb$$. The output on $$q_0$$ is $$X Y Z$$. Priority does not matter here.

Thus, the output would be $$\{ a^n b^n c^n \}$$, which is not regular.