Let $L$ be a regular language. Prove that:

  1. $L_{+--}=\left\{w: \exists_u |u|=2|w| \wedge wu\in L\right\}$

  2. $L_{++-}=\left\{w: \exists_u 2|u|=|w| \wedge wu\in L \right\}$

  3. $L_{-+-}=\left\{w:\exists_{u,v} |u|=|w|=|v| \wedge uwv\in L\right\}$

are regular and:

  1. $L_{+-+}=\left\{ uv:\exists_w |u|=|w|=|v| \wedge uwv\in L \right\}$

is not regular.

Seems very hard to me. I suppose 1-3 are similar (but I may be wrong), but I don't know how to approach. General idea is usually to modify finite state machine for $L$ to accept other language. But those constructions are often very sophisticated and I still can't come up with it alone.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.