I want to build a context sensitive grammar for the language $\{a^{2^n}\mid n\geq 0\}$. I think it should be something like this \begin{align*} S &\to aA \mid a\\ aA&\to aaaA \mid aa \end{align*}


This is from Hopcroft and Ullman's book, Example 9.4, pg 220:

$$ S \rightarrow ACaB $$ $$ Ca \rightarrow aaC $$ $$ CB \rightarrow DB $$ $$ CB \rightarrow E $$ $$ aD \rightarrow Da $$ $$ AD \rightarrow AC $$ $$ aE \rightarrow Ea $$ $$ AE \rightarrow \epsilon $$

Update: in fact given grammar is unrestricted which can be modified as a context sensitive.

But if your ultimate goal is to prove that the given language is a CSL, then it is enough to create a linear bounded automaton - a TM whose computational ability is restricted to the portion of input. In other words, the head of the TM cannot move beyond the input area. LBA's and CSG's are equivalent.

You can just erase one input symbol at a time starting from the right, and each time you erase one symbol increase a counter by one (binary symbols 0 and 1) which are stored in place of erased symbols. When you erase all input symbols check if the counter is of the form 100...0. If yes then accept, otherwise reject). 100...0 means it is a power of 2.

enter image description hereenter image description here

  • $\begingroup$ Is this really context sensitive? There is CB -> E which i think should not be in context sensitive grammar $\endgroup$ – unnamed Jun 4 '17 at 19:44
  • $\begingroup$ No, what I have sent is unrestricted grammar. But you can modify it and rewrite as CSG (which is given in the example 9.5 on pg. 224 of the same book), which is not trivial. Note also "Almost any language one can think of is context sensitive; the only known proofs that certain languages are not CSL's are ultimately based on diagonalization" $\endgroup$ – fade2black Jun 4 '17 at 20:03
  • 1
    $\begingroup$ can you show me how to transform the given grammar in context sensitive ? $\endgroup$ – unnamed Jun 4 '17 at 21:04
  • $\begingroup$ See original post's update. $\endgroup$ – fade2black Jun 4 '17 at 21:26
  • $\begingroup$ But the language should accept also the word a, when n is 0 $\endgroup$ – unnamed Jun 5 '17 at 11:58

I just had this as a homework and would like to share an IMO much simpler and more intuitive solution than the one from the textbook.

$$ \begin{align*} S&\rightarrow EAE\ |\ a\ |\ aa\\ EA&\rightarrow E2A\ |\ TA\\ 2A&\rightarrow AA2\\ 2AE&\rightarrow AAE\\ TA&\rightarrow aaaaT\\ TAE&\rightarrow aaaa \end{align*} $$

$E$ marks beginning and end. $2$ marks that we do another doubling of our number of $A$s and whenever a $2$ is inserted, it then "walks" over the whole string, doubling all $A$s it passes. $T$ is used to translate the $A$s into $a$s. We translate $A$ to $aaaa$ instead of $a$, so that our grammar is context sensitive.


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.