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.
Best Answer
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$