Can a Non-Deterministic Pushdown Automaton recognize $ \# a^nb^{2^n} \# $ which a TM can?
Actually this language is not a CFL.



And here is a proof:

Let's take string $w: a^mb^{2^m}$ where $m$ is constant guaranteed by pumping lemma for CFLs.

Then $a^{m+k_1}b^{2^m+k_2} \in L$ where $1\le k_1,k_2&lt;m$

(cases invloving either $k_1 = 0$ or $k_2=0$ are easier.)

Now, that suggests that,

$2^{m+k_1} = 2^m + k_2$ (by defination of $L$)

$\therefore 2^m2^{k_1} = 2^m + k_2$   ....................................(1)

now, $k_1 \ge 1\implies 2^m2^{k_1} \ge 2^m + 2^m &gt; 2^m + k_2.$

(because we have $k_1 \ge 1$ this means left side of equation $1$ will always have value $\ge 2.2^m$ but right side of equation can have maximum value of $2^m + m - 1$)

Hence this language can't be CFL.