For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular?

[Where $w^R$ is the reverse of $w$]

My intuition says it is, as for a regular $L$, the languages $L^*$, $\{y: xyz\in L\}$ and $L^R$ are all regular languages, but I wasn't able to build a DFA/NFA for it, as if I try and "guess" from where to reverse the word I lose track of if it's a word in the original language. Any hints?

  • 2
    $\begingroup$ Non-determinism is a good idea; combine that with how the automaton for $L^R$ works. $\endgroup$
    – Raphael
    Apr 27 '17 at 18:11

Assume we have automaton $\mathcal A$ for regular language $L(\mathcal A) = L$. It is possible to construct a new finite automaton for the new language $L'=\{xy^Rz\mid xyz\in L\}$. You need nondeterminism and extra components in the states to remember the choices made.

It is also possible to use closure properties. Let $\mathcal A_{p.q}$ be the automaton $\mathcal A$, except that initial state is $p$ and final state is $q$. Similarly $\mathcal A_{p.F}$ for final states $F$.

Now $L'= \bigcup_{p,q} L(\mathcal A_{q_0,p})\cdot L(\mathcal A_{p,q})^R\cdot L(\mathcal A_{q,F})$.

  • $\begingroup$ I have failed building an NFA even when trying to remember the choices made, as it just seemed like there are too many different branches and it became to hard for me to keep the information from jumbling up. The second approach did work for me though. Though I don't think I would have ever thought of iterating over pairs of states like that (my attempt was using the first and final letter of each section, but it failed as well). The idea here made it simple and was surprisingly easy to prove formally. Thank you! $\endgroup$
    – Nescio
    Apr 27 '17 at 22:59

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.