1
$\begingroup$

I've proven that the Turing-recognizable languages are closed under concatenation and I need to show that they are closed under homomorphism.

But what's really the difference? Doesn't closure under concatenation imply homomorphism as well? Or perhaps I misunderstand what homomorphism means when talking about Turing-Recognizable languges?

$\endgroup$
4
$\begingroup$

A class of languages $\mathcal{L}$ is closed against concatenation if for every pair of languages $L_1, L_2 \in \mathcal{L}$ we also have $L_1 \cdot L_2 \in \mathcal{L}$.

Here, $A \cdot B = \{ v \cdot w \mid v \in A, w \in B \}$.

A class of languages $\mathcal{L}$ is closed against homomorphism if for every language $L \in \mathcal{L}$ and every (word) homomorphism $f$ we also have that $f(L) \in \mathcal{L}$.

Here, $f : \Sigma \to \Sigma^*$ is lifted to words and sets in the natural way, i.e.

$\qquad\displaystyle f(w) = f(w_1) \dots f(w_n)$ for $w = w_1 \dots w_n$,

and

$\qquad\displaystyle f(A) = \{ f(w) \mid w \in A\}$.

(Note that can make a difference if you require $f : \Sigma \to \Sigma^+$.)

It's easy to see that the two are not the same.

Let $A = \{ w \in \{a, b\}^* \mid |w|_a \in 2\mathbb{N} \}$. Clearly, $\mathcal{A} = 2^A$ is closed against concatenation but not against homomorphism.

Let $B = \{ ww \mid w \in \{a,b\}^* \}$. Then, $\mathcal{B} = 2^B$ is closed against homomorphism but not against concatenation.
(mentioned by chi in a comment)

For completeness, $2^{\Sigma^*}$ is closed against both, and $\mathcal{A}\cdot\mathcal{B}$ against neither.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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