# Pumping lemma occurrence of c > d

I'm trying to prove a language is not regular through using pumping lemma, but can't seem to come up with any way of doing it.

The alphabet is:

$$\Sigma = \{c, d\}$$

The language is:

$$A = \{z \in \Sigma^* \mid c(z) > d(z)\} , \text{where c(w) and d(w) means occurrences of c or d\in z }$$

I tried to define a string like so:

Pumping length = P

$$s = c^{(P+1)}d^P$$

Here is how I tried to solve it:

If we select P = 5. Then s = ccccccddddd and split it in 3 parts. Where x = ccccccd, y = ddd and z = d. (Is that even allowed though as |xy| <= P, but now |xy|=10 and 10>5). If I then do y^2. Then I get s = ccccccdddddddd, so now d>c which proves the string is not in the language. Does this then prove that the language is not regular?

• I suggest you keep trying. – Yuval Filmus Apr 29 '19 at 12:13
• Have been stuck for quite some time so I don't think that will help. @YuvalFilmus – Android999 Apr 29 '19 at 12:24
• You won’t understand the material if other people solve all exercises for you. This is a relatively simple application of the pumping lemma, so it’s there to help you practice the basics. – Yuval Filmus Apr 29 '19 at 12:39
• Yes I do know this is probably basics, but I would like an answer that I then could look back on when solving the other exercises in the future. @YuvalFilmus – Android999 Apr 29 '19 at 12:47
• I seems you are on the right track, but try to switch the order of $c$'s and $d$'s in your string, so $s = d^p c^{p+1}$. – AcId Apr 29 '19 at 12:51

You need to show that with that arbitrary pumping length $$P$$, for any partition $$c^{(P+1)}d^P = xyz$$ such that $$|y|>0$$ and $$|xy|\leq P$$, there is some $$i$$ such that $$xy^iz \not\in A$$.
Since for any partition we require that $$|xy|\leq P$$, then $$x$$ and $$y$$ necessarily consist only of $$c$$'s. Also, you know that $$|y| >0$$ (it's also a requirement). Can you find an $$i\in\mathbb{N}$$ such that the amount of $$c$$'s in $$xy^iz$$ is less than or equal to the amount of $$d$$'s?
You need to pick a string that's in the language (i.e., has fewer $$d$$s than $$c$$s) but, when pumped, creates strings that are not in the language (more $$d$$s than $$c$$s). Think about how you can achieve that.
• @Android999 you can't claim to know what $p$ is, nor can you define $x$, $y$, or $z$. The answer is given here. Carefully review the laws of the lemma and make sure you understand this answer – lox Apr 29 '19 at 14:05
• @Android999 That's not quite right, for the reasons that lox points out and because we require $|xy|\leq P$. But the language is strings of $c$s and $d$s in any order, which mean you can choose a similar $s$ which makes your life easier. Or you could choose a different number of repetitions for $y$, which can also be made to work. – David Richerby Apr 29 '19 at 14:11