Proofs using the regular pumping lemma

Problem Detail: 

I have two questions:

1. I consider the following language $$L_1= \{ w\in \{0,1\}^* \mid \not \exists u\in \{0,1\}^* \colon w= uu^R\}.$$ In other words $w$ is not palindrome with even length. I proved that this language is NOT regular by proving that its complement is not regular. My question is how to prove it using the pumping lemma without using going over the complement.

2. Let $$L_2=\{w\in\{0,1\}^* \mid \text{$w$ has same number of 101 substrings and 010 substrings}\}. $$ I proved that this language is not regular by using equivalence classes. How I can prove it using the pumping lemma?

Thanks alot for edit:)

Asked By : farseer

Answered By : farseer

After long thinking i think i answered 2.

we choose string (010)^N(101)^N , where N is pumping length. No matter what y we will choose, xy^0z will have more 101 then 010. the idea is that we can only add more 101 sub strings in first part of string or remove some 010 sub strings.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7235