1
$\begingroup$

We have a language $$ L = \{\text{w element of } \{a,b\}^* \mid \#(a,w) = \#(b,w)^2 \} $$ where $ \#(a,w) $ means the number of letters $a$ in $w$

I would like to show that this language is not context-free.

Assume that L is context-free. Let p be the constant from Pumping Lemma.

$$ w = a^{p^2}b^p $$

Let uvxyz be the decomposition of w as in the lemma. Since $ \mid vxy \mid \le p $ we have to consider three cases:

  1. $v$ and $y$ contain only letters from block of $a$'s
    In this case $s'=uv^2xy^2z$ should be the part of language L. But number of letters b in $s'$ is p and number of letters a is more then $p^2$. Contradiction $s' \notin L$.
  2. Similar explenation when $v$ and $y$ contain only leters from block of $b$'s
  3. $vxy$ contains letters $a$ and $b$

    But how to show contradiction in this case?
$\endgroup$

2 Answers 2

1
$\begingroup$

The third case breaks down into several sub-cases, but the only difficult sub-case is the one in which $v=a^k$ and $y=b^\ell$ for some $k,\ell>0$ with $k+\ell\le p$. Then

$$uv^nxy^nz=a^{p^2+(n-1)k}b^{p+(n-1)\ell}\;.$$

For convenience let $m=n-1$, and suppose that $(p+m\ell)^2=p^2+mk$; then $$2pm\ell+m^2\ell^2=mk\;,$$ and hence either $m=0$, or $2p\ell+m\ell^2=k$, and hence

$$m=\frac{k-2p\ell}{\ell^2}\;.$$

Thus, apart from $n=1$ (i.e., $m=0$) there is at most one non-negative integer $n$ such that $uv^nxy^nz\in L$.

$\endgroup$
0
$\begingroup$

In the 3rd case there exist constants $c_1, c_2>0$, such that

$$\#(a,uv^nxy^nz)\le c_1 n$$

but

$$\#(b,uv^nxy^nz)\ge c_2 n.$$

Then you have $c_1 n \ge (c_2 n)^2.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.