1
$\begingroup$

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.

$\endgroup$

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.