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.

  • $\begingroup$ Are you talking about isomorphism of labeled multigraphs, or simply of the underlying multigraph? In the former case, I guess that $M$ is minimal iff $\varphi(M)$, so it maybe isn't what you are considering. $\endgroup$ Apr 12, 2015 at 10:38
  • $\begingroup$ @M: I don't think so. Anyhow, I meant isomorphism of labelled multigraphs, where the labels can be also acted on. $\endgroup$
    – domotorp
    Apr 12, 2015 at 12:03
  • $\begingroup$ can you give more bkg on the origination of the idea? coincidentally somewhat similar to this recent question on GSM rearranging, invite further discusssion in Theoretical Computer Science Chat $\endgroup$
    – vzn
    Apr 13, 2015 at 2:08

1 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.

  • $\begingroup$ This is a useful condition (though not entirely precise, as in the isomorphism I also want to allow permutations of the states, your condition is easy to modify to include this). However, I am looking, if exists, for some (maybe not necessary and sufficient) condition that is easier to apply. $\endgroup$
    – domotorp
    Apr 12, 2015 at 12:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.