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!
 A: 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)    
