When does automaton stay unchanged after string homomorphism?

Question

Suppose we have a string homomorphism $\varphi: \Sigma \rightarrow \Sigma^*$. Consider the languages in $\varphi(\Sigma^*)$ whose letters are elements of $\varphi(\Sigma)$, so here I do not want to expand each $\varphi(\Sigma)$, but leave them in this abstract form, e.g., $\varphi(a)\varphi(b)\varphi(a)$ would be a word. So in fact for any language $L$, the language $\varphi(L)$ is the same as $L$, over a different alphabet. If $M$ was an automaton over $\Sigma$, then there is a natural automaton, $\varphi(M)$, over $\varphi(\Sigma)$ with the same number of states: from any given state after reading $\varphi(a)$, $\varphi(M)$ goes to whatever state $M$ would go after reading all letters of $\varphi(a)$.

For example, suppose that $M$ was counting the parity of $b$'s, that is, from state 0 it goes to state 1 iff the read letter is $b$, and vica versa. Let $\varphi$ map $a$ to $\varphi(a)=ab$ and $b$ to $\varphi(b)=bab$. Then $\varphi(M)$ goes from state 0 to state 1 iff the read letter is $\varphi(a)$. Therefore, $M$ and $\varphi(M)$ are isomorphic. In fact, for the above $M$, we get an isomorphic automaton if and only if exactly one of $\varphi(a)$ and $\varphi(b)$ have an odd number of $b$'s.

In general, for what $M$ and $\varphi$ will be $\varphi(M)$ isomorphic to $M$?

If it makes the question simpler, we can ignore which states are accepting and which is the start state. I am interested in any type of conditions, as I could not find anything on the subject. I am also curious when $\varphi(M)$ will be minimal for the language it recognizes.

Answer 1

Let $\mathcal{A} = (Q, A, \cdot, q_0, F)$ be the minimal DFA of your language $L$. If I understand correctly, you would like to have a permutation $\sigma$ on $A$ such that $$ q \cdot \varphi(a) = q \cdot \sigma(a) $$ for every state $q$ and letter $a$. This will happen if and only if, there exists $\sigma \in \mathfrak{S}(A)$ such that, for each letter $a$, $$ \varphi(a) \in \bigcap_{q \in Q} L(q, q \cdot \sigma(a)) $$ where, given two states $p$ and $q$, $L(p, q) = \{u \in A^* \mid p \cdot u = q\}$.

For instance, in your example, you get the following conditions when $\sigma$ is the identity \begin{align} \varphi(a) \in L(0,0) \cap L(1,1) &= \{ u \in A^* \mid |u|_b \text{ is even }\} \\ \varphi(b) \in L(0,1) \cap L(1,0) &= \{ u \in A^* \mid |u|_b \text{ is odd }\} \\ \end{align} and the following conditions when $\sigma$ is the transposition $(1\ 0)$ \begin{align} \varphi(a) \in L(0,1) \cap L(1,0) &= \{ u \in A^* \mid |u|_b \text{ is odd }\} \\ \varphi(b) \in L(0,0) \cap L(1,1) &= \{ u \in A^* \mid |u|_b \text{ is even }\} \\ \end{align} which, altogether, gives your condition.