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

but why are considering only 0^2k2^2k4^2k    in this order   040404042222 and many more strings like this also belong to the language isn't it?

---

You can consider any X which belongs to L.

---

then how will you get to know what is U   V   &  W   ? in order to pump and show that it does not follow the pumping lemma

---

I think that  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 but it can occur in any  order , be it e.g. - 004242, 042024..............

L={002244  ...........................all permutations of this string  +

00002222244444............all permutation of this string          +

 +so no .........}

what do you say ?

---

I am not denying it. I never said that 0,2 and 4 should come in some particular order. They can come in any order. Pumping lemma says that if you are considering any string say X which belongs to L and has the length larger than the number of states in a DFA, then after dividing X into u,v,w according to constraints, for all i uvⁱw belongs to L.

Here for proving you can take any X belonging to L.So, I took one valid X belonging to L in the above proof. You can take any other X and still prove the same. 

If you still have a doubt what we can do is tell me which X I should pick to prove that L is not regular.

---

 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.