Доказательство того, что язык является регулярным

Лемма о накачке используется для доказательства того, что язык не является регулярным. Но каким может быть язык
оказался регулярным? В частности,

Let L be a language. Define half(L) to be  
{ x | for some y such that |x| = |y|, xy is in L}.  
Prove for each regular L that half(L) is regular.  

Есть ли какой-нибудь трюк или общая процедура для решения таких вопросов?