1

I'm trying to prove that the following language is not regular via the Pumping Lemma. But I don't know, why is my procedure wrong (choosen word is incorrect according to my teacher).

$$L= c^+ \cdot \left\{w \in \{a,b\}^* \mid \text{count of a's in w} = \text{count of b's in w}\right\}$$

I choose word $w=c^2a^nb^n$

$$ \begin{array}{l} w = xyz \\ x = c^2a^l \\ y = a^k \\ z = a^{(n-k-l)}b^n \end{array}$$

I have choosen $i=5$: then $w = c^2a^la^{5k}a^{(n-k-l)}b^n = c^2a^{(n+4k)}b^n \implies w $ is not from $L$ because $n+4k > n$

Why is $ca^nb^n$ good choice and $c^2a^nb^n$ is a bad choice? Why I'm wrong? Thanks

Adam
  • 1,946
Milwoukee
  • 31

1 Answers1

2

Watch out what the pumping lemma states! There exists a natural number $n$ such that any word of length $\ge n$ can be written as $xyz$ such that $|xy|\le n$, $y\ne\epsilon$ and all $xy^iz$ with $i\ge 0$ are in $L$.

You want to consider $c^2a^nb^n\in L$. At least if $n\ge 2$, this might split as $x=c$, $y=c$, $z=a^nb^n$ (recall that we only have $|xy|\le n$, not $=n$). Now the pumping lemma gives us $ca^nb^n, c^3a^nb^n$ and so on - and that is not the desired contradiction as these actually are in $L$!

However, if you consider $ca^nb^n$, then these possibilities arise :

  • $x=ca^k$, $y=a^l$ with $k\ge 0$, $l\ge1$, $k+1\le n$ leading to the contradiction e.g. $xy^0z=ca^{n-l}b^n\in L$.
  • Or $x=\epsilon$, $y=ca^k$ with $0\le k\le n-1$, leading to the contradiction $xy^0z=a^{n-1}b^n\in L$.
Hagen von Eitzen
  • 374,180