Problem Detail:
Let $L$ be a regular language. Prove that:
- $L_{+–}=left{w: exists_u |u|=2|w| wedge wuin Lright}$
- $L_{++-}=left{w: exists_u 2|u|=|w| wedge wuin L right}$
- $L_{-+-}=left{w:exists_{u,v} |u|=|w|=|v| wedge uwvin Lright}$
are regular and:
- $L_{+-+}=left{ uv:exists_w |u|=|w|=|v| wedge uwvin 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.
Asked By : xan
Answered By : Yuval Filmus
Here is a proof that the language $L_0 = { w : exists_u |u|=|w| land uw in L }$ is regular. It can be modified to show that the first three on your list are regular. (Note that I changed $wu$ to $uw$.) Given a DFA for $L$, we build an NFA for $L_0$. The first thing that the NFA does is guess (take an $epsilon$ move) a state $q$, whose intended semantics is the state that the DFA for $L$ ends up after reading $u$. It then simultaneously runs two copies of the DFA for $L$, one starting at the start state and the other starting at $q$. On reading a symbol $a$, it moves according to an arbitrary symbol on the first, and moves according to $a$ on the second. A state is accepting if the first copy is at state $q$ and the second is at an accepting state. For the final one, consider the language $L= a^+ b^+ c^+$, and intersect $L_{+-+}$ with $a^+ c^+$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11785
