1
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • $\begingroup$ $x, y \in (a, b) ^*$? $\endgroup$
    – user19121278
    Jun 17 at 10:14
  • $\begingroup$ @user19121278 No, they are part of $L$ $\endgroup$
    – Math4me
    Jun 18 at 8:46

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ 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! $\endgroup$
    – Math4me
    Jun 17 at 10:26
  • $\begingroup$ @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. $\endgroup$
    – user19121278
    Jun 17 at 10:28
  • $\begingroup$ An infinite union of regular languages isn't necessarily regular. It's also not necessarily non-regular. $\endgroup$
    – Yuval Filmus
    Jun 17 at 10:30
  • $\begingroup$ @YuvalFilmus infinite union of $\epsilon$ isn't regular? $\endgroup$
    – user19121278
    Jun 17 at 10:31
  • $\begingroup$ An infinite union of regular languages could be either regular or non-regular; both options happen. $\endgroup$
    – Yuval Filmus
    Jun 17 at 10:32

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.