1
$\begingroup$

I need to prove that the language $\mathscr L=\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma

My try:

$\{a,b\}^*=\{\epsilon,a,b,aa,ab,ba,bb,aaa,aab,\dots\}$

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$

Now let as choose the word $\color{blue}{x=b^na^k}$ such that $n>k$ and also $|x|\geq n$ so we can use $(1)-(3)$

$(1):$

$x=\underbrace{bbbbbbbb\dots}_{\text{n times}}\underbrace{aaa\dots}_{\text{k times}}$

$uv$ will contain only '$b$' therfore $u=b^{\psi},\,\,\,v=b^{\varphi}$

$(2):$

$\psi \geq 0,\,\,\,\,1\leq \varphi \leq n$

$(3):$

Let as choose $\color{blue}{i=??}$ so $uv^iw=b^{\psi}(b^{\varphi})^{n+1}w\in \mathscr L$

I'm difficult choosing the word '$\color{blue}x$' and choosing $\color{blue}i$ to come to contradiction with the lemma

$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

Remember here that the pumping lemma works downwards as well as upwards. The string $b^n a^k$ is of the form $u v b^r a^k$ where $r \geq 0$; the pumping lemma lets us deduce that $u b^r a^k$ is also in the language.

So you just need to pick $k=n-1$, and you get a contradiction straight away.

$\endgroup$
6
  • $\begingroup$ I did not understand your answer in the second line "$ub^ra^k$ is in the language" so $\color{red}{u\underbrace{b^r}_{=v}\underbrace{a^k}_{=w}}$? $\endgroup$
    – 3SAT
    Dec 4, 2015 at 8:59
  • $\begingroup$ $b^r \not = v$. I've labelled by $b^r$ all the $b$'s that are left after we've labelled $uv$. So if $u = b^3, v = b^2, x = b^6 a^4$, then we would have $r = 1, k = 4$. $\endgroup$
    – Patrick Stevens
    Dec 4, 2015 at 9:01
  • $\begingroup$ so where is the $v$ disapeard in the second line $ub^ra^k$? Thanks for your time and attention $\endgroup$
    – 3SAT
    Dec 4, 2015 at 9:12
  • $\begingroup$ We need to pump v and in your answer you pumping a $\endgroup$
    – 3SAT
    Dec 4, 2015 at 9:20
  • $\begingroup$ I'm not pumping $a$. I'm pumping $v$. Instead of making more copies of $v$, though, I'm removing one copy. That's what I meant by "the pumping lemma works downwards as well as upwards": it lets you set $i = 0$ as well as $i > 1$. $\endgroup$
    – Patrick Stevens
    Dec 4, 2015 at 9:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .