Prove that a language is not regular.

Question

I want to ask how to prove the following language is not regular using closure properties. I tried to use pumping lemma but I find the proof itself shaky. I'd appreciate if you can help.

The language is $ L = \{0^{i}1^j0^k, where\ i+j \neq k\}$.

When I applied pumping lemma. I picked $s=1^k0^{k+1}$. Then I pump up, let s=wxy, then $wx^iy$ must be in L. But the length $|x|$ would have to be 1 for this proof to work, which I think is shaky...

I'd appreciate your help!

Answer 1

The $i+j \neq k$ condition is quite annoying to work with. I didn't check but I suspect $L$ actually satisfies the pumping lemma, despite being not regular.

Using closure property, you can try to bring the problem back to another well knwon non-regular language, on which the proof using pumping lemma works well. The point is that, here somehow a potential automaton for this language should discriminate (when $i=0$) words like $1^{k}0^{k}$ to reject them, but $L'=\{1^{k}0^{k} \mid k \geq 0\}$ is well-known for not being regular (straight-forward proof using pumping lemma).

Now, here is a more formal proof : if $L$ was regular, then its intersection with the regular language $1A^*$ of words beginning with $1$, which is $L \cap 1A^* = \{1^{j}0^{k} \mid j \neq k\}$ should be regular. Taking the complementary language, it should again remain regular (regular languages are closed by intersection and complementation). Then, intersecting the complementary with $1^*0^*$ (to rule out all other complicated words induced by the complementation) it should be regular, but you get $L'$.

Answer 2

I think the modified pumping lemma is still the easiest for this case.

Let p be the pumping length

$ S = {0^{p}1^p0^{2p!} } $

Now this string can be written as $ wyz $ , where $ wy^{n}z$ belongs to the regular language L. Now y can only be $ 0^{l}$ or $ 1^{l}$, otherwise pumping it would break the whole structure of the string. Now you just need to realize that such a y when pumped would break the condition for $ i + j \neq k $ for any value of l, since any value of l would be a factor of $2p!$ and can be pumped to ensure that it equals $2p!$.