Question

I'm trying to show that L6={cnambp:n+m=p,p?6} is not regular. I need a little help, I was practicing the pumping lemma, and I encountered this language, I saw these conditions and got totally confused, what to do now?

Earlier I showed that L5={anbn:n?0} is not regular. In this Language it was very simple to choose w, namely w=apbp, where p is the pumping length. But this new Language is complicated, so I thought you guys could help me out.

Answer 1

Let L be a regular language. Then there exists an integer p?1 (depending only on L) such that every string w in L of length at least p (p is called the "pumping length") can be written as w=xyz (i.e., w can be divided into three substrings), satisfying the following conditions:

1. |y|?1
2. |xy|?p and
3. for all i?0, xyiz?L.
   y is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in L).

(1) means the loop y to be pumped must be of length at least one; (2) means the loop must occur within the first p characters. There is no restriction on x and z.

In simple words, For any regular language L, any sufficiently long word w?L can be split into 3 parts. i.e w=xyz, such that all the strings xykz for k?0 are also in L.

Now let's consider an example. Let L={(01)n2n?n?0}.

To show that this is not regular, you need to consider what all the decompositions w=xyz look like, so what are all the possible things x, y and z can be given that xyz=(01)p2p (we choose to look at this particular word, of length 3p, where p is the pumping length). We need to consider where the y part of the string occurs. It could overlap with the first part, and will thus equal either (01)k+1, (10)k+1, 1(01)k or 0(10)k, for some k?0 (don't forget that |y|?1). It could overlap with the second part, meaning that y=2k, for some k>0. Or it could overlap across the two parts of the word, and will have the form (01)k+12l, (10)k+12l, 1(01)k2l or 0(10)k2l, for k?0 and l?1.

Now pump each one to obtain a contradiction, which will be a word not in your language. For example, if we take y=0(10)k2l, the pumping lemma says, for instance, that xy2z=x0(10)k2l0(10)k2lz must be in the language, for an appropriate choice of x and z. But this word cannot be in the language as a 2 appears before a 1.

Other cases will result in the number of (01)'s being more than the number of 2's or vice versa, or will result in words that won't have the structure (01)n2n by, for example, having two 0's in a row.

Don't forget that |xy|?p. Here, it's useful to shorten the proof: many of the decompositions above are impossible because they would make the z part too long.

Each of the cases above needs to lead to such a contradiction, which would then be a contradiction of the pumping lemma. Voila! The language would not be regular.