1
$\begingroup$

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.

|cite|improve this question|||||
$\endgroup$
2
$\begingroup$

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.

Alternative hint: guess the middle point (non-deterministically), then...

Since this is an exercise problem, I am giving only a hint, not a full solution. Try solving it yourself.

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ Is it as simple as understanding if given L := {foobar, food} then we can say the L^R := {raboof, doof} is also regular, then prove that the HALF(L) := {rab, do} is regular, and by the same theorem that HALF(L)^R := 2HALF(L) := {bar, id} is regular. As far as guessing a middle point, you mean by that guessing a start state for the language 2HALF(L), of which I assumed you have an epsilon transition to every non-accept state in the original DFA, and this new NFA will work? I am having trouble with that because it seems it would accept strings that were not right. $\endgroup$ – QIANG Sep 12 '14 at 13:53
  • $\begingroup$ I take it as a yes? $\endgroup$ – QIANG Sep 14 '14 at 3:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.