# Can a Non-Deterministic Pushdown Automaton recognize $\# a^nb^{2^n} \#$ which a TM can?

$$\# a^nb^{2^n} \#$$

such that

• The alphabet of the machine is {, a, b, x}.

• The symbol x will never appear on the input a.

• The contents of the tape at completion may be anything.

• The head begins on the lefthand #.

• n ≥ 0.

I know that a Turing machine could recognize this language. But can a NPDA recognize this language too? I am thinking it can but I do not know how to start proving how/why?

• What do you remember about grammars and machines? – greybeard Dec 9 '19 at 4:53

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

(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 > 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.

• is my understanding correct that because it is not a CFL, there doesn't exist any PDA or NPDA that can recognize the language, right? – bluewander Dec 9 '19 at 5:10
• Yes you're right. – Vimal Patel Dec 9 '19 at 5:11
• i am starting to get it but i was confused how did you get here... $k_1 \ge 1\implies 2^m2^{k_1} \ge 2^m + 2^m > 2^m + k_2.$ Would you mind breaking it down a bit? – bluewander Dec 9 '19 at 5:19
• sure I'll edit the answer. – Vimal Patel Dec 9 '19 at 5:20
• No, to prove a language context sensitive you have to show that there is a TM that decided it using space atmost linearly proportional to length of input. – Vimal Patel Dec 9 '19 at 9:33

No pushdown automaton can recognize this language, because the language is not context-free. This can be shown using the pumping lemma for context-free languages or Parikh's theorem. The latter gives a particularly straightforward proof: the language is not context-free because $$2^n$$ cannot be written as a finite union of linear functions.

The language is context-sensitive. This can be seen by noting that it is possible to write a program that counts the number of a's and b's and checks whether they are correct using linear space. Such a program can be converted into a linear bounded automaton by the standard methods of transforming programs into Turing machines. Context-sensitive grammars are so powerful that it is often easier to think of them as being arbitrary programs with a linear space restriction, rather than grammars in the usual sense.

• I see. I also thought so but I forgot about using the pumping lemma for this. I haven't heard about Parik's theorem though. For the TM that recognizes this, I'm stuck with knowing how to move the tape head when it reads $b$. I am not sure how does it count $2^n$ for it to know when to move left and right. – bluewander Dec 9 '19 at 5:12
• @Andrew If you are trying to write a Turing machine that recognizes the language and you are stuck, I would suggest asking a separate question just for that. Editing your question with the additional question is probably a bad idea because it invalidates the current answers. – Aaron Rotenberg Dec 9 '19 at 5:18
• is this language described context sensitive? – bluewander Dec 9 '19 at 8:35
• @bluewander See the edit to my answer. – Aaron Rotenberg Dec 9 '19 at 13:20
• @bluewander, btw you can construct TM which given a input checks whether it has form $a^*b^*$. If yes for every $a$ it erases exactly half of $b$'s that are present. That way TM for language in question can be constructed. I haven't fully constructed that. This is just a idea which might not work. – Vimal Patel Dec 10 '19 at 0:59