# Proving that language is regular or not regular

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.

• possible duplicate of How to prove that a language is not regular? May 4, 2013 at 23:58
• I am not sure that your statements are correct because it seems by Myhill–Nerode theorem that the first three languages have infinitely many equivalence classes ! for the first one : take $w_i$ be the i-th in $L_{+--}$ and $w_{i+1}$ be the (i+1)-th word then for every i one can choose $u_i$ to show that there exists a word that separate the classes of $w_i$ and $w_{i+1}$ May 4, 2013 at 23:58
• @Fayez What if, for example, $L=\Sigma^*$? Then $L_{+--} = \Sigma^*$ has just one equivalence class. Go over your proof and see what goes wrong. May 5, 2013 at 3:17
• @Bartek and any other one voting to close: half of the question is actually about proving that certain operations on languages conserve the property of being regular. May 5, 2013 at 3:25

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^+$.

• I don't see that. $L=a^+b^+c^+ \Rightarrow L_{+-+} \cap a^+c^+=\left\{ a^n c^m: n+m\equiv_2 0 \right\}$, which is clearly a regular language. But I suppose I'm wrong :) Can you point me the right direction?
– xan
May 5, 2013 at 12:41
• I've managed to modify your construction of $L_0$ and even remove $\varepsilon$ moves so it become more elegant (in my opinion). So the first three problems solved and thank you for that! :) But the only one thing I ask you for is to clarify the final one and my concerns in comment above. I would be very grateful.
– xan
May 5, 2013 at 13:28
• When I compute $L_{+-+} \cap a^+ c^+$ I get something else. Note that every word in $L$ must contain a $b$. May 5, 2013 at 15:13
• Sorry, but I don't know how to compute $L_{+-+}\cap a^+c^+$. I suppose that the result is $\left\{ a^n c^n: n\in\mathbb{N}\right\}$ which gives us what we want, but I just don't know how to justify that.
– xan
May 5, 2013 at 16:01
• Ok, I can see now :-)
– xan
May 5, 2013 at 16:25