Suppose $L$ is a regular language over $\Sigma$ and we want to show that $$\frac{1}{2}L = \{x \in \Sigma^* \mid \exists y \in \Sigma^* (xy\in L \wedge |x| = |y|)\}$$ is regular. I thought of taking the set of even length strings over $\Sigma^*$ (given by $(00\cup01\cup10\cup11)^*$) and then interescting with $L$, which would be regular because the intersection of regular languages is regular. Then, the set of prefixes of this language is regular (by a previous exercise), but that's useless because that set of strings isn't actually the set $\frac{1}{2}L$. In particular, we didn't constrain the prefixes to be the ones with equal length suffixes.

Baically, I'm really stuck on how to make a FA that recognizes the length of the strings. Namely, given $x$ how do we add $\epsilon$ transitions to arrive at $xy$ with $|x| = |y|$, which we then pass in $xy$ to the FA for $L$? Thanks in advance, I've been scratching my head on this for a while.


Given a DFA $A$ for $L$, construct an NFA which operates as follows:

  • The NFA starts by guessing a state $q$ which will be the state that $A$ is on after reading $x$.
  • The NFA will maintain two states, $q_1,q_2$, the first initialized at the initial state of $A$, the second initialized at $q$.
  • For each symbol $\sigma$ read, the NFA guesses a new symbol $\tau$ (which corresponds to a symbol in $y$), and advance $q_1$ using $\sigma$ and $q_2$ using $\tau$.
  • The NFA is at an accepting case if $q_1 = q$ and $q_2$ is an accepting state of $A$.
  • $\begingroup$ Thank you for the reply. I understand why this works, since esentially $q_1 = q$ means we landed at $x$ and $q_2 \in F$ means $xy \in L$. However, I wanted to clarify what you mean by guessing $\tau$- these are epsilon transitions to other states in $A$ right? $\endgroup$ – user131539 Feb 3 at 19:12
  • 1
    $\begingroup$ The NFA has no epsilon transitions (assuming you allow multiple initial states). You should advance $q_1$ and $q_2$ in parallel. $\endgroup$ – Yuval Filmus Feb 3 at 19:13
  • $\begingroup$ Ok. So then every state in $A$ is an initial state, because a priori we have no idea where $x$ ends up in $A$? $\endgroup$ – user131539 Feb 3 at 19:18
  • $\begingroup$ Right, $q$ could be any state of $A$. $\endgroup$ – Yuval Filmus Feb 3 at 19:57
  • $\begingroup$ Thank you for the explanation! $\endgroup$ – user131539 Feb 3 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy