Proving that the language $\mathscr L$ is non regular using the pumping lemma

117 Views Asked by At

I need to prove that the language $\mathscr L=\{\text{all the binary words such that the number of ones divide the number of zeros}\}$ is non regular using the pumping lemma

For example: $010010\in \mathscr L$ because that there are fore zeros and two ones and $4\big|_2$ but $11000100 \notin \mathscr L$ because that there are $5$ zeros and $3$ ones and $5 \nmid _3$

My try:

Suppose that $\mathscr L$ is regular so $\exists$ a word '$x$' with length of at least $n$

$|x|\geq n $ such that

$(1)\,\,\,|uv|\leq n$

$(2)\,\,\,|v|\geq 1$

$(3)\,\,\,uv^iw \in \mathscr L\,\,\,\,\,i\geq 0$

Now, let as choose the word $\color{blue}{x=0^n1^k}$ such that $n \big |_k$ $|x|\geq n$ so we can use $(1)-(3)$

$x=uv0^{\gamma}1^k$

So $u=0^{\alpha}$ and $v=0^{\beta}$

$\Longrightarrow x=\underbrace{0^{\alpha}}_{\color{blue}u}\underbrace{\big (0^{\beta}\big )}_{\color{blue}v}\,^{\color{blue}i}\underbrace{0^{\gamma}1^k}_{\color{blue}w}$ such that ($\alpha+\beta+\gamma) \big |_k$

I'm stuck here

EDIT: Attempt number $2$

Let as choose the word $x=0^n1^n$ $x\in \mathscr L$ because $|x|=2n$ so $\exists n \in \mathbb{N}$ such that $(1)-(3)$ applying

Now $x=\underbrace{0^{\alpha}}_{\color{blue}u}\underbrace{\big (0^{\beta}\big )}_{\color{blue}v}\,^{\color{blue}i}\underbrace{0^{\gamma}1^k}_{\color{blue}w}$ let as choose $\color{blue}{i=2}$ $x=0^{\alpha}\big(0^{\beta}\big)\,^20^{n-\alpha-\beta}1^n=0^{n-\beta}1^n$ and $\beta \geq 1$ so for $i=2$ $x\notin \mathscr L$ contradiction to the lemma $\square$

1

There are 1 best solutions below

2
On BEST ANSWER

You have the pumping lemma stated a bit wrong. It says that there exists an $n$ such that for all $x$ with $|x|>n$ we can write $x=uvw$ where your three criterion hold.

Your choice of string doesn't wind up working out very well, as the following shows: now, we have $k|(\alpha+\beta+\gamma)$, and want to find an $i$ such that $k\not|\alpha+i\beta+\gamma$. Consider this mod $k$. $\alpha+\gamma = -\beta$, so $\alpha+i\beta+\gamma=(i-1)\beta$. The assertion we wish to prove is that $\forall\beta,k\exists i$ such that $(i-1)\beta\neq 0$ (mod $k$). But there are cases where this is true, specifically when $\beta=0$ (mod $k$).

A better string to choose would be $1^\alpha0^\alpha$. For large enough $\alpha$, $v$ must be comprised solely of $1$'s, and then you just make the number of $1$'s greater than the number of $0$'s.