Show that $\{a^ib^jc^{2j}\mid i\ge 0,j\ge 0\}$ is not regular

1.1k Views Asked by At

How can I show this?I don't know how to start.

Show that the set given below is not regular. $$\{a^ib^jc^{2j}\mid i\ge 0,j\ge 0\}$$

1

There are 1 best solutions below

10
On BEST ANSWER

Suppose that the language is regular, I will use Brian M.scott's idea if $p$ is the pumping leangth choose the word $z:=b^pc^{2p}$, we will use the pumping lemma for regulal languages

$|z|>p$ so $z=uvw$ such that

  1. $|uv|\leqslant p$

  2. $|v|\geqslant 1$

  3. $uv^iw\in \mathcal L\quad i\geqslant 0$

For $i=2$ or $i=0$ the word is not in the language, therefore the language isn't regular.