1
$\begingroup$

I am trying to prove that the following language is regular:

$L'$ is a clone of $L$ where $L$ is a regular language over $\{0,1\}^*$. For example, if $L=001$, then $L'=000011$.
If $L=010$, $L'=001100$. Show that $L'$ is regular.

I know there are several methods I could use here, such as finding a regular expression, sketching a DFA/NFA or deriving a regular grammar but I am not sure how to do so for this particular language. Any ideas? Thanks.

$\endgroup$

1 Answer 1

1
$\begingroup$

If I understand correctly, a clone is obtained by applying the monoid homomorphism $f:\{0,1\}^* \to \{0,1\}^*$ defined by $f(0) = 00$ and $f(1) = 11$.

Now, it is a standard result that regular languages are closed under homomorphims. In particular, the clone of a regular language is a regular language.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .