Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am studying for my next midterm for formal languages and finite state machines.
I am stuck with this problem.
Determine whether this language is context free or not.
The language is : $$ L = \{ a^n b^j | n \leq j^2 \} $$

I tried designing a PDA for it but to no avail because I cant keep track of when j exceed square root of n using the stack.
So my assumption is that it is not context free.
However, I am not that good with the pumping lemma.
This is what I tried:
Assume L is context free.
Let $ w=a^mb^m $ with w in L.
By the pumping lemma w can be decomposed as
w = uvxyz with |vxy| <= m and |vy|>=1 such that $uv^ixy^iz$ is in L with i>=0

case 1
aa...a ab...b
uvxy z

Now, I have a problem I don't know how to chose i so the resulting string is not in L. Any help would be appreciated.

share|improve this question
add comment

3 Answers

Note: I misread the problem, and as a result this argument shows that the language $$L=\Big\{a^kb^\ell\in\{a,b\}^*:k^2\le\ell\Big\}$$ is not context free, rather than the one in the question. I’m leaving it posted, since the technique may be useful to someone else, but please refer to Rick Decker’s answer for a demonstration that the language in the question is not context-free.


Suppose that $L$ is context-free, and let $p$ be the pumping length; we may assume that $p>1$. Let $m=\lfloor\sqrt p\rfloor$, and let $w=a^mb^p\in L$. Then we can write $w=uvxyz$ in such a way that $|vxy|\le p$, $|vy|\ge 1$, and $uv^kxy^kz\in L$ for each integer $k\ge 0$. Since $m<p$, the string $vxy$ must have the form $a^kb^\ell$ for some integers $k$ and $\ell$ such that $\ell\ge 1$.

  • If $k=0$, then $uxz$ has $m$ $a$’s but fewer than $m^2$ $b$’s, so it’s not in $L$; thus, $k>0$.

  • If $v=a^r$ for some $r>0$, and $y=a^sb^t$, then $uv^ixy^iz$ has $$m+(i-1)r+(i-1)s=m-r-s+(r+s)i$$ $a$’s and $$p+(i-1)t=p-t+ti$$ $b$’s. But $$\lim_{i\to\infty}\frac{p-t+ti}{(m-r-s+(r+s)i)^2}=0\;,$$ so $uv^ixy^iz\notin L$ for sufficiently large $i$.

Only one possibility remains.

  • If $v=a^kb^r$ for some $r>0$ and $y=b^t$, $uv^ixy^iz$ has $$m+(i-1)k=m-k+ki$$ $a$’s and $$p+(i-1)r+(i-1)t=p-r-t+(r+t)i$$ $b$’s, and as in the previous case we see that $uv^ixy^iz\notin L$ for sufficiently large $i$.

This shows that $L$ is not context-free.

share|improve this answer
add comment

Let $p$ be the integer of the Pumping Lemma and, as Hendrik suggested, let $w=a^{p^2}b^p\in L$. Then, the PL implies that we can write $w=uvxyz$, with $|vy|\ge 1, |vxy|\le p$ and $uv^ixy^ix\in L$ for all integers $i\ge 0$. Using Hendrik's observation that neither $v\text{ nor }y$ can contain both $a\text{ and }b$ (since then $uv^2xy^2z$ wouldn't be of the correct form to be in $L$), we have three possible cases:

  1. $v=a^r, y=a^s$
  2. $v=a^r, y=b^s$
  3. $v=b^r, y=b^s$

With $0<r+s\le p$ in each case.

In case (1), $uv^2xy^2x=a^{p^2+r+s}b^p$ and this isn't in $L$, since $p^{2+r+s}>p^2$.

In case (2), $uv^ixy^iz=a^{p^2+(i-1)r}b^{p+(i-1)s}$ and it's not hard to show that $p^2+(i-1)r>(p+(i-1)s)^2$ whenever $i-1>s^2/(r-2ps)$. Since $r\text{ and }s$ cannot both be zero, we can always find such a value for $i$.

In case (3), $uxz=a^{p^2}b^{p-r-s}$ and this isn't in $L$ since $p^{2}>(p-r-s)^2$.

Done. Three more or less simple cases.

share|improve this answer
    
@Brian Look at the original. We require $a^nb^j$ with $n\le j^2$. Sure looks like $n=p^2\le(p)^2 =j^2$ to me. –  Rick Decker Oct 25 '12 at 14:57
    
You’re right: evidently I mentally turned it around to get $n^2\le j$. –  Brian M. Scott Oct 25 '12 at 15:29
add comment

The first thing to do is find a good initial word, in the language, not random $a^mb^m$ which must be from another example.

Choose $w = a ^{n^2} b^n$ which is of proper form. Assuming $L$ is context-free we have a decomposition, as you state yourself. The pumping segments $v$ and $y$ each cannot contain both symbols $a$ and $b$ since pumping them would lead to $b$'s after $a$'s, which cannot happen in $L$.

Now you start considering cases, and show that pumping always leads to strings outside $L$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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