0

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!

y123liu
  • 117

2 Answers2

0

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!$.

user2277550
  • 2,194
0

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'$.

yago
  • 2,120
  • thanks for helping me! I want to ask what does A mean in 1A*? – y123liu May 14 '14 at 14:19
  • You're welcome. $A$ just means the alphabet you're using, but I guess it is just ${0,1}$ in your case and $$ is the Kleene operator. So $1A^$ is just the regular expression for the language of words beggining with a $1$, and then anything. You could write it (if $A$ is indeed just $0$s and $1$s) : $1.(0 + 1)^*$ – yago May 14 '14 at 14:24