$\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

is also valid.

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

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

You can take a look here for more details, or the best is to take a look at this book, which contains proofs about basic properties of regular languages.

  • $\begingroup$ 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)? $\endgroup$
    – FUZxxl
    Oct 28 '13 at 19:36
  • $\begingroup$ I updated my answer. $\endgroup$
    – bellpeace
    Oct 28 '13 at 20:11

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