1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ What did you try? Where did you get stuck? $\endgroup$ – David Richerby 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$ – Yuval Filmus Jan 13 '17 at 11:37
4
$\begingroup$

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.

$\endgroup$
  • $\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.