Proving a language with equal occurences of ab, and cd is not a regular language using the Pumping Lemma

Question

I am trying to show that $A = \{w \in \{a,b,c,d\}^{*}|w \textrm{ has equal occurences of } ab \textrm{ and } cd\}$ is not regular by using the Pumping Lemma.

My idea here was to use the string $ s = (ab)^{p}(cd)^{p} $. Clearly, $ s \in A $, and $ |s| = 2p \geq A $. So the the three conditions of the pumping lemma hold.

Where I am stuck is picking the correct decomposition of $ s $. My idea was to do the following:

We can decompose $ s $ into $ xyz $ such that:

• $ x = (ab)^{j}, j \geq 0 $
• $ y = (ab)^{k}, k \geq 1 $
• $ z = (ab)^{p-j-k}(cd)^{p} $

Now consider if we "pumped" $ y $. Let $ i = 2 $. Then $ xy^{2}x = (ab)^{j}(ab)^{2k}(ab)^{p-j-k}(cd)^{p} = (ab)^{p+k}(cd)^{p} \notin A $. Therefore, we arrived at a contradiction and $ A $ is not a regular language.

But my confusion here is that the $ xyz $ I have chosen is not the only decomposition of $ s $. For example, you could choose $ x = a $, $ y = b $, and $ z $ is the rest of the string. Do I have to cover all possible cases? If so, this seems like a bad choice for $ s $ -- any other ideas?

Another concern is that my chosen decomposition violates the condition $ |xy| \leq P $ of the Pumping Lemma will not hold for $ p = 1 $.

Answer 1

Ok I will split the answer into two parts, one for each of your questions \ concerns \ confusions:

---

Q: Are we allowed to use the pumping lemma if we chose a specific decomposition, or do we need to show for all decompositions?

A: The pumping lemma states, $\exists p.\forall w.|w|\ge p \rightarrow \exists x,y,z.w=xyz \land\text{ they are a valid decomposition }\land\forall k\in\mathbb{N}.xy^kz\in A$.

and you are trying to show the negation of this statement. as you can see, there is an "exists" sign before the "x,y,z" and therefore in the negation there will be a "for all" sign.

Thus, you MUST go over ALL possible decompositions in order to use the pumping lemma in this way.

---

Q: This doesn't work for $p=1$ but works for every other value of $p$. is this a problem?

A: no! its absolutely fine.

Say, for example, you know how to prove for $p=5$ and you don't know how to do $p=1$. define $w=(ab)^5(cd)^5$, and you know that $|w|\ge 5 \ge 1=p$. but since $|w|\ge 5$ and you know how to solve for $p=5$, you know how to deal with $w$.

This means that its enough to prove for some value of $p$ and all other values BELOW it will be automatically proved too!

---

Also, you are in the right direction. This is a good choice of a word, but you will need to work a bit more to show that every decomposition cannot be always pumped.

I hope this helped you a bit :)

Answer 2

You need to consider all possible decompositions. There aren't so many cases to consider:

1. $x \in (ab)^*$, $y \in (ab)^+$.
2. $x \in (ab)^*$, $y \in (ab)^*a$.
3. $x \in (ab)^*a$, $y \in (ba)^+$.
4. $x \in (ab)^*a$, $y \in (ba)^*b$.

Go over them one by one.