<p>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\}$.</p>

<p>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) &amp;= \{ u \in A^* \mid |u|_b \text{ is even }\} \\
 \varphi(b) \in L(0,1) \cap L(1,0) &amp;= \{ 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) &amp;= \{ u \in A^* \mid |u|_b \text{ is odd }\} \\
 \varphi(b) \in L(0,0) \cap L(1,1) &amp;= \{ u \in A^* \mid |u|_b \text{ is even }\} \\
\end{align}
which, altogether, gives your condition.</p>

CC BY-SA 3.0
2015-04-12T12:23:50.303Z
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.
domotorp
CC BY-SA 3.0
2015-04-12T09:01:37.397Z
2015-04-12T09:01:37.397Z
J.-E. Pin
<p>Suppose we have a <a href="http://en.wikipedia.org/wiki/String_operations#String_homomorphism">string homomorphism</a> $\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)$.</p>

<p>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.</p>

<blockquote>
  <p>In general, for what $M$ and $\varphi$ will be $\varphi(M)$ isomorphic to $M$?</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2015-04-12T10:38:31.100Z
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.
Michaël Cadilhac
CC BY-SA 3.0
2015-04-12T12:03:43.420Z
@M: I don't think so. Anyhow, I meant isomorphism of labelled multigraphs, where the labels can be also acted on.
domotorp
CC BY-SA 3.0
2015-04-13T02:08:04.590Z
can you give more bkg on the origination of the idea? coincidentally somewhat similar to this recent question on [GSM rearranging](http://cstheory.stackexchange.com/questions/31008/generalized-sequential-machine-gsm-rearranging-correspondence), invite further discusssion in [chat]
vzn
<graph-theory><automata-theory><graph-isomorphism><dfa><homomorphism>
When does automaton stay unchanged after string homomorphism?
domotorp
# When does automaton stay unchanged after string homomorphism?

(Asked by: username_0 on 2015-04-12)

Suppose we have a [string homomorphism](http://en.wikipedia.org/wiki/String_operations#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.

**Tags:** graph-theory, automata-theory, graph-isomorphism, dfa, homomorphism

> **Comments:**
> **username_1**: 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.  
> **username_0**: @M: I don't think so. Anyhow, I meant isomorphism of labelled multigraphs, where the labels can be also acted on.  
> **username_2**: can you give more bkg on the origination of the idea? coincidentally somewhat similar to this recent question on [GSM rearranging](http://cstheory.stackexchange.com/questions/31008/generalized-sequential-machine-gsm-rearranging-correspondence), invite further discusssion in [chat]  

---

## 1 answers

### Answer by username_3 on 2015-04-12. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  

---

