Automata | Prove that if $L$ is regular than $half(L)$ is regular too

I've see couple of approaches to this kind of questions yet I have no clue how to approach this one.

Let L be regular language, and let $half(L)$ be: $half(L) = \{u \mid uv \in L\ s.t. |u|=|v|\}$. Prove that if $L$ is regular then $half(L)$ is regular too.

I tried to make a new regular language, $Even(L)$ that recognizes all the even words in $L$ (due to the fact that if we want to slice in half the total length must be even) and from there to "capture" the half words. But I still think it isn't quite correct.

Would like to understand the logic behind a proper solution rather than just the solution :)

Thanks!

Solution 1:

Let $A = (\delta_A, Q, q_0, F)$ be a DFA for $L$ (in some alphabet $\Sigma$).

Then define $B$ as follows:

• The states $Q_B$ of $B$ are of the form $[q,S]$ where $q \in Q$ and $S \subseteq Q$.
• The initial state of $B$ is $[q_0, F]$.
• $\delta_B([q,S],a) = [\delta_A(q,a), T]$ where $T = \{p \in Q: \exists b \in \Sigma: \exists p' \in S: \delta_A(p,b) = p' \}$
• The accepting states of $B$ are $F_B = \{[q,S] : q \in S \}$.

Then we have the following invariant by construction: all reachable states $[q,S]$ after some input are such that $q$ is the state that $A$ would be in after reading that input, and the states in $S$ are all those states such that there is a path from that state to an accepting state (in $A$) that has the same length as the input that was read.

This holds for the initial state (no input, so the only state $A$ could be in is $q_0$ and the only accepting states on no input are those in $F$).

The way the transition rule is defined also upholds the relation: the first part just does what $A$ would have done on that extra letter, and we update the states so that there is a path to an accepting state that is 1 step longer. We could formally prove it by induction on the length of the input.

And when we are in a state $[q,S]$ with $q \in S$ after reading some input $w_1$, we know that $q$ is the state of $A$ after reading $w_1$ and as $q \in S$ there is some input $w_2$ with $|w_1| = |w_2|$ that induces a path from $q$ to an accepting state, which means that $w_1w_2 \in L$, and so $w_1 \in \operatorname{half}(L)$.

(source: this solution, a bit reformulated)