8
$\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$
  • $\begingroup$ possible duplicate of How to prove that a language is not regular? $\endgroup$ – Bartosz Przybylski May 4 '13 at 23:58
  • $\begingroup$ 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}$ $\endgroup$ – Fayez Abdlrazaq Deab May 4 '13 at 23:58
  • $\begingroup$ @Fayez What if, for example, $L=\Sigma^*$? Then $L_{+--} = \Sigma^*$ has just one equivalence class. Go over your proof and see what goes wrong. $\endgroup$ – Yuval Filmus May 5 '13 at 3:17
  • $\begingroup$ @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. $\endgroup$ – Yuval Filmus May 5 '13 at 3:25
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – xan May 5 '13 at 12:41
  • $\begingroup$ 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. $\endgroup$ – xan May 5 '13 at 13:28
  • $\begingroup$ When I compute $L_{+-+} \cap a^+ c^+$ I get something else. Note that every word in $L$ must contain a $b$. $\endgroup$ – Yuval Filmus May 5 '13 at 15:13
  • $\begingroup$ 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. $\endgroup$ – xan May 5 '13 at 16:01
  • $\begingroup$ Ok, I can see now :-) $\endgroup$ – xan May 5 '13 at 16:25

Your Answer

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

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