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!
Best Answer
Let $A = (\delta_A, Q, q_0, F)$ be a DFA for $L$ (in some alphabet $\Sigma$).
Then define $B$ as follows:
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)