$L \subseteq \Sigma^*$ is a regular language.

Show that the following language

$L/2 = \{x \in \Sigma^* \mid \exists y \in \Sigma^* : xy \in L, |x| = |y| \}$

is a regular language as well by describing how you change an arbitrary given DFA for $L$ to another DFA or NFA which accepts $L/2$.

About $L/2$, it only accepts the first even half of the word which is from the language $L$. As example, $aaabbaba \in L$, then $aaab \in L/2$.

So a DFA for $L$ is already given and now we need to change it so it works for $L/2$. What seems important to me at first, is the length of the word. It needs to have an even length else it won't work taking the first half of the word which has an even length (this is required by $L/2$). For this reason, we also need to know the total length of the word accepted by $L$. We then divide it by 2 and set an end state when we reached the first half.

Hmm it doesn't really seem to work like that because this is specially designed for a specific word but we need to take care of any word with any even length..

Can you give me some hints / ideas?

  • 1
    $\begingroup$ See here: cs.stackexchange.com/questions/11785/… One idea is to construct an NFA and leverage nondeterminism to "guess" when you are halfway through the string, and then verify that your guess is correct. $\endgroup$
    – theyaoster
    Nov 6 '17 at 0:24