Proving Regularity of Languages that are 1/k of an already known regular language
Let $L$ be a regular language and let $(p, q) \in \mathbb{N}^2$. Then the following language is regular:
$$
  L_{p,q} = \{ u \in A^* \mid  \text{there exist $x$ and $y$ in $A^*$ such that $|x| = p|u|$, $|y| = q|u|$ and $xuy \in L$} \}
$$
Furthermore, for any subset $S$ of $\mathbb{N}^2$, the language 
$$
  L_S = \bigcup_{(p,q,r) \in S} L_{p,q}
$$
is also regular. I would like to insist that it works for any any subset $S$, including non recursively enumerable subsets of $\mathbb{N}^2$, which might look a little bit suspicious at first glance...

You can try to prove these results by using automata, but it is much easier to use the fact that a language is regular iff it is recognized by a finite monoid. 

Let $L$ be a regular language of $A^*$. It is recognized by a finite monoid $M$, that is, there is a surjective monoid morphism $f:A^* \to M$ and a subset $P$ of $M$ such that $f^{-1}(P) = L$. Now $\mathcal{P}(M)$, the powerset of $M$, is also a finite monoid under the multiplication defined, for $X, Y \in \mathcal{P}(M)$, by $XY = \{ xy \mid x \in X, y \in Y\}$. 

Let now $h: A^* \to \mathcal{P}(M) \times M$ be the monoid morphism defined, for each letter $a \in A$, by $h(a) = (f(A), f(a))$. Then for each word $u$, $h(u) = (f(A^{|u|}), f(u))$. I claim that $L_{p,q} = h^{-1}(Q)$ where 
$$
   Q = \bigl\{(R,m) \in \mathcal{P}(M) \times M \mid R^pmR^q \cap P \not= \emptyset \bigr\}.
$$
and similarly $L_S = h^{-1}(T)$ where 
$$
   T = \Bigl\{(R,m) \in \mathcal{P}(M) \times M \mid \Bigl(\bigcup_{(p,q) \in S}R^pmR^q\Bigr) \cap P \not= \emptyset \Bigr\}.
$$
Thus $L_{p,q}$ and $L_S$ are recognized by the finite monoid $\mathcal{P}(M) \times M$ and hence are regular.

Proof of the claim.
\begin{align*}
  h^{-1}(Q) &amp;= \{u \in A^* \mid (f(A^{|u|}), f(u)) \in Q \} \\
  &amp;= \{u \in A^* \mid f(A^{p|u|}f(u)f(A^{q|u|}) \cap P \not= \emptyset \} \\
  &amp;= \{u \in A^* \mid f(A^{p|u|}uA^{q|u|}) \cap P \not= \emptyset \} \\  
  &amp;= \{u \in A^* \mid A^{p|u|}uA^{q|u|} \cap f^{-1}(P) \not= \emptyset \} \\
  &amp;= \{u \in A^* \mid A^{p|u|}uA^{q|u|} \cap L \not= \emptyset \} \\
  &amp;= L_{p,q}
\end{align*}