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.