$ \# 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?

  • $\begingroup$ What do you remember about grammars and machines? $\endgroup$
    – 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<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 > 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.

  • $\begingroup$ 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? $\endgroup$
    – bluewander
    Dec 9 '19 at 5:10
  • $\begingroup$ Yes you're right. $\endgroup$ Dec 9 '19 at 5:11
  • $\begingroup$ 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? $\endgroup$
    – bluewander
    Dec 9 '19 at 5:19
  • $\begingroup$ sure I'll edit the answer. $\endgroup$ Dec 9 '19 at 5:20
  • 1
    $\begingroup$ 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. $\endgroup$ 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.

  • $\begingroup$ 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. $\endgroup$
    – bluewander
    Dec 9 '19 at 5:12
  • $\begingroup$ @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. $\endgroup$ Dec 9 '19 at 5:18
  • $\begingroup$ is this language described context sensitive? $\endgroup$
    – bluewander
    Dec 9 '19 at 8:35
  • $\begingroup$ @bluewander See the edit to my answer. $\endgroup$ Dec 9 '19 at 13:20
  • $\begingroup$ @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. $\endgroup$ Dec 10 '19 at 0:59

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.