# If $L$ is regular then $\{x~|~\exists y ~~s.t~~ xyx^R \in L\}$ is regular

Prove/disprove the following claim:

If $$L\in RL$$ then $$\{x~|~\exists y ~~s.t~~ xyx^R \in L\} \in RL$$

I think that this is true, and my intuition is by using $$L_{pq}$$ s.t:

For every $$(p,q)\in Q\times Q$$ define $$L_{pq}=\{w|\delta'(p,w)=q\}$$.

Then by using $$L_{pq}○L_{q,q'}○(L_{pq})^R$$ and taking the union of all possible pairs, do we get the desired result?

Thanks!

• $x, y \in (a, b) ^*$? Jun 17 at 10:14
• @user19121278 No, they are part of $L$ Jun 18 at 8:46

Start with an automaton for $$L$$, with states $$Q$$, initial state $$q_0$$, final states $$F$$, and transition function $$\delta$$. Construct a new automaton whose set of states is $$Q \times 2^Q$$. After reading a word $$x$$, the new automaton should be at state $$\langle \delta(q_0,x), \{q : \delta(q,x^R) \in F\} \rangle.$$ I will let you complete the definition of the automaton.
• Thank you! I didn't mean the infinite union, but: $\bigcup_{(q,f)\in (Q\times F) } L'_{qf}$, such that $L'_{qf}$ is defined as the concatenation above. I will now think about your proof idea as well, thanks! Jun 17 at 10:26
• @YuvalFilmus if we choose every time $x=\epsilon$ and remaining would be considered as $y$, then $$L = \bigcup_{x \in L} \{x\}=\epsilon$$, then we said it's regular? Also because $xyx^r$ is also regular. Jun 17 at 10:28
• @YuvalFilmus infinite union of $\epsilon$ isn't regular? Jun 17 at 10:31