Let 1 2 3 4 and C w in w the number of 1s equals the num

Let = {1, 2, 3, 4} and C = {w ^* | in w, the number of 1s equals the number of 2s, and the number of 3s equals the number of 4s}. Show that C is not context free.

Solution

We use the pumping lemma to prove the claim. Consider the string s = 1 p3 p2 p4 p , where p is the pumping length. Since the pumping lemma states |vxy| p, we consider two scenarios. In the first scenario, vxy contains only one kind of symbol in the alphabet, assume that symbol is a. In such case, by pumping up, the resulting string will have more a than all other three symbols, thus the resulting string is not in L. In the second scenario, vxy contains two kind of symbols. In such case, by pumping up, either the requirement that 1 and 2 have same number is violated, or the requirement that 3 and 4 have same number is violated. Thus, the resulting string is not in L. Hence, by now, we have proved the claim.