How to show that a language {w|ww^R in A} is regular, A being regular?

Question

Been working on my homework and I've been stuck on a question for over a week now. Not really asking for a solution but if someone could point me towards the right direction that would be great, as I have literally no idea of how to go about this. A previous question asked us to show that for any DFA that accepts A, we can create a NFA that accepts {w^R | w in A}, which was pretty easy (just reverse the DFA).

This question asks: Show that if A is a regular language, then so is {w|ww^R in A}, where w^R is the reverse of the string w.

I know that if I have two regular expressions, then their concatenation is also a regular expression, that's simple. But this asks me to show that the first-half of some of the strings in A is a regular expression. No idea how to show that this is true. It's not even intuitive to me that this is true, except that the question implies it is.

Anyone got any idea of where to start about this? Thanks!

Answer 1

You might want to study If $L$ is a regular language then so is $\sqrt L=\{w\mid ww∈L\}$.

The solution is to simulate the DFA in parallel with itself, from both sides of the string. For each letter one step forward (for $w$) and one step backward (for $w^R$). If the forward state reading $w$ reaches the same state as the backward simulation, both parts joined form a computation on $ww^R$.