# Show that the regular languages are closed against taking “the second half” [duplicate]

Given $L$ is regular, the proof that $\mathrm{HALF}(L)$ is regular is pretty straightforward to me (e.g., #11 in this link): simply making a NFA and meeting in the middle with 2 original DFAs, the creation of such NFA proving it is regular.

However, what if you wanted to prove the 2nd half string is regular, not the 1st half of a string. That is,

$$\mathrm{2HALF}(L) = \{ x\mid yx\in L \text{ for some }y\text{ with } |y|=|x|\}\,.$$

Compare this to the standard

$$\mathrm{HALF}(L) = \{ x\mid xy\in L \text{ for some }y\text{ with } |y|=|x|\}\,.$$

I struggled on a solution, trying to use the same method as used on $\mathrm{HALF}(L)$ but can't seem to wrap my head around it.

## marked as duplicate by FrankW, Juho, David Richerby, Raphael♦Sep 12 '14 at 12:19

Hint: if $L$ is regular, the reversal $L^R$ of the language $L$ is regular; see How to show that a "reversed" regular language is regular. You should be able to use this fact.