pumping lemma

Question

is the language regular or not ?

$\Sigma={0,1,2,3,4}$ 

L={ w $ \varepsilon \Sigma $* ||w|₀mod 2=0,|w|₀=|w|₂= |w|₄}

 if not how will it be proven by pumping lemma?

Answer 1

We can describe the given language as a set of all strings over alphabet having EQUAL and EVEN numbers of 0's,2's and 4's.

Let DFA for the given language has K states.

Take X= 0^2k2^2k4^2k which belongs to L.(as 2k will be the even number and the number of 0's=number of 2's =number of 4's).

Now however you divide the string into u,v,w "pumping part" will always contain all 0's only as K<2K.

So after dividing X into u,v and w, if we pump 'v' part for, 'm' times we will get AT LEAST 'm' additional 0's.

but, 0^2k+m2^2k4^2k ∉ L as the number of 0's > number of 2's and 4's.

Hence language is not regular.

 

According to me, L is a CSL.

@arjun sir please check whether the proof is correct or not.

 

 

 

Comments

 what does 0^2k2^2k4^2k mean then?

---

i didn't have doubt but I just wanted to know in general case what will be u v w

---

0^2k2^2k4^2k

Is one of the strings which belongs to L. It can be 000000002222222244444444 if k=4.