How to approach regular languages using the pumping lemma?

Question

I have struggles understanding how generally approach and test regular languages using the pumping lemma. Givent the following language:

$L = \{ \text{s} \mid \text{s} \in \{ c, d \}^* \land |s|_c = |s|_d \}$

I would like to test whether it contains the words $cccdd$ and $cdcdcd$ and whether I'm dealing with a regular language at all.

What I have tried sofar is to use the definition of pumping lemma:

Condition 1. $|v|≥1$

Condition 2. $|uv|≤n$

Condition 3. $∀_i∈N_0 :uv^iw∈L$

So I have tried first check whether the language is regular but struggle to come up with a proof:

I assume that a word contains $|s|_c = |s|_d$ an equal amount of $c$ and $d$. Thus $|c^n * d^n| = 2n$. If I reformulate $cd$ into $uvw$, then $uv$ has to consists only of $c$. Based on condition Condition 1. $|v|≥1$ there are more $c$ then $d$ which contradicts the language definition.

Appreciate any insights regarding how to formulate a correct proof and test it.

Answer 1

In order to use the pumping lemma, you assume your language $L$ is regular. That means there exist $N$ such that every word $w$ in $L$ can be written $w = xyz$ with $|xy|<N$ and $\forall k\in \mathbb N, xy^kn \in L$.

Then, you have to find a word (depending on $N$), that can't check that condition and prove it, and then you have a proof by contradiction.

$c^Nd^N$ is a good one in that case, as in any working decomposition $xyz$, $y$ cannot contain any $d$ since $|xy|<n$. Therefore :

• $|xy^2z|_c = |xyz|_c + |y|_c >|w|_c$
• $|xy^2z|_d = |xyz|_d = |w|_c$

This is a contradiction since $xy^2z\in L$.