# Does a language stay regular if you re-encode the input? [duplicate]

$\tau$ be a transformation that, applied to a word of $\Sigma_a^\star$, replaces each character with a word from a possibly different $\Sigma_b^\star$ and concatenates the resulting words. For instance, given a $\tau$ with the following translation table:

A -> AA
B -> AB
C -> BA
D -> BB


$\tau(ABC)=AAABBA$ and $\tau(DACB)=BBAABAAB$. Note that the words may not all have the same length. A translation table such as

A -> FOO
B -> BAR
C -> BAZ
D -> QUUX


is also valid.

Now, is $\{w'|w\in L\land w'=\tau(w)\}$ regular iff $L$ is a regular language as well?

• What did you try? Where did you get stuck? Oct 28 '13 at 13:44
• @David I don't have the slightes clue how to prove this. Not homework. Oct 28 '13 at 14:55
• This question is better than the one its a duplicate of, but that one already has good answers.
– Raphael
Oct 29 '13 at 12:31
• @Raphael I've nominated this for reopening as the duplicate has been deleted. Jan 13 '17 at 9:56
• @Raphael Perhaps we should move the answers from the deleted questions here? Or at least undelete that question? Jan 13 '17 at 11:37

The answer is yes. This is generally called homomorphism, and regular languages are closed under homomorphism. Moreover, regular languages are closed under inverse homomorphism also. More precisely, if $\tau$ is a homomorphism from alphabet $\Sigma$ to alphabet $\Delta$ and $L$ is a regular language over $\Delta$, then $\tau^{-1}(L)$ is also a regular language.
• The proof in the link you gave me seemingly only covers one direction (namely, that if $L$ is regular, so is $\tau(L)$). What about the other direction (if $\tau(L)$ is regular, then $L$ is regular)? Oct 28 '13 at 19:36