-1
$\begingroup$

How do I being to show that if $L_{1}$ is Turing-recognizable language over $\Sigma=\{0,1\}$, then $L_{2} = \{ww^R | w ∈ L_{1} \}$ is a Turing recognizable language too.

There is another similar problem, but instead of the language being recognizable, it's decidable. If anyone has any ideas on how to approach both of these problems, I'd be very thankful.

I'm very new to this topic and didn't find any similar problems online, so I'm looking for any kind of tips to solve these problems :)

$\endgroup$

2 Answers 2

0
$\begingroup$

The following is a description of an acceptor/decider for $L_2$. If the length $|x|$ of the input $x$ is odd, then reject. Otherwise consider the subword $x_1$ (resp $x_2$) consisting of the first (resp. last) $|x|/2$ symbols of $x$. Check whether $x_1 = x_2^R$. If that is not the case, then reject. Otherwise, simulate an acceptor/decider for $L_1$ on input $x_1$.

$\endgroup$
2
  • $\begingroup$ Does this also help to show that language is also Turing-recognizable? $\endgroup$
    – bireugit
    Commented May 1, 2022 at 12:58
  • $\begingroup$ Yes. This shows that if $L_1$ is recognizable, then $L_2$ is recognizable. Moreover, if $L_2$ is decidable, then $L_2$ is decidable. $\endgroup$
    – Steven
    Commented May 1, 2022 at 15:00
0
$\begingroup$

Here is what a $TM$ for $L_2$ would do

We first check that input $x$ is not of odd length, if so we reject

Next we cut $x$ into two halves and check that the second half is the reversal of the first, hence the string is of the form $ww^R$

Next, we run the recogniser/decider of $L_1$ on $w$ (the first half of the input $x$), and output whatever it outputs

So we basically do whatever the recogniser/decider for $L_1$ does on $w$, but only after checking that the string $x$ is in the form $ww^R$ (which can be done in few steps)

Hopefully its clear that we would yield a recogniser/decider for $L_2$ form a recogniser/decider for $L_1$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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