Show that the language $L$ is not regular

56 Views Asked by At

I want to show that the below language is not regular:

$$L=\{\text{words that contain exactly } k \text{"a" }, m \text{"b" and } n \text{"c" , where }k,m,n\geq 1 \text{ and } m=k\cdot n\}$$

For that we use the Pumping Lemma, right?

Then we suppose that it is regular and the langyage contains all the words of the form $pq^{(\ell)}r$ with $n\geq 0$.

Then we have to find a counterexample with the middle part. That means since in the middle the part is repeated, will the number of a, b, c will not satisfy anymore the relation $m=k\cdot n$ ?

1

There are 1 best solutions below

2
On

Pumping lemma For any regular language L, there exists an integer $n$, such that for all $x \in L$ with $|x| \geqslant n$, there exists $u, v, w \in \Sigma^*$, such that $x = uvw$, and

  1. $|uv| \leqslant n$
  2. $|v| \geqslant 1$
  3. for all $i \geqslant 0$, $uv^iw \in L$

Now, consider the word $x:= a^nb^2c^{2n} \in L$. The word v given by the pumping lemma above is of the form $a^k$ for $1 \leqslant k \leqslant n$. You can pump arbitrarily many "a"s without touching the rest.