Theorem: If $A$ is regular, then the language of left-halves of strings in A:

$$A_h = \setbuilder{x}{\exists y \tst |x| = |y| \tand xy \in A}$$

is also regular.

---

Proof: Since $A$ is regular, there is a DFA $M = (Q, \Sigma, \delta, q_0, F)$ accepting $A$. Write the states as $Q = \set{q_0, q_1, \dots, q_{n-1}}$. We construct an NFA $M_h = (Q_h, \Sigma, \delta_h, q_{0h}, F_h)$ as follows.

Take $Q_h = Q^{n+1}$, and $q_{0h} = (q_0, q_0, q_1, \dots, q_{n-1})$. We maintain a 'prime' copy of the DFA $M$, which will start at $q_0$. We then run $n$ other machines simultaneously. Each of these machines starts at a different state from $Q$, and takes all possible transitions at each step. Then an input string is accepted if and only if the 'prime' copy is in a state $x$ at the same time as the copy started from $x$ is in a final state.

So, we further define:

$$\delta_h(q, x) = \set{\delta(q, x)} \times \underbrace{\bigcup_{y \in \Sigma} \set{\delta(q, y)} \times \dots \times \bigcup_{y \in \Sigma} \set{\delta(q, y)}}_{n \text{ times}}$$

And finally,

$$F_h = \setbuilder{(q_k, x_0, \dots, x_{n-1})}{x_k \in F}$$

So this machine accepts $A_h$, and $A_h$ is regular.