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

1 Answer 1

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.