# Context sensitive grammar for $\{a^{2^n}\mid n\geq 0\}$

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*}

• What had you tried? Jun 4, 2017 at 20:36
• Not a duplicate, but Raphael's answer to another question is relevant here and mostly answers this question. May 20, 2019 at 7:29

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.

• Is this really context sensitive? There is CB -> E which i think should not be in context sensitive grammar Jun 4, 2017 at 19:44
• 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" Jun 4, 2017 at 20:03
• can you show me how to transform the given grammar in context sensitive ? Jun 4, 2017 at 21:04
• See original post's update. Jun 4, 2017 at 21:26
• But the language should accept also the word a, when n is 0 Jun 5, 2017 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.

The shortest non-contracting grammar we could come up with is: \begin{align*} S&\rightarrow a\ |\ LR\\ L&\rightarrow LD\ |\ D\\ Da&\rightarrow a^2D\\ DR&\rightarrow aR\ |\ a^2 \end{align*}

• L marks the left side of the word, produces the doubling symbol D, and can only be eliminated by conversion to a D.
• D is moved through the word from left to right, doubles each a and can only be eliminated on an R.
• R marks the right side of the word and also acts like an a, to accomplish non-contraction in the rules. It can only be eliminated with a D.

The shortest non-trivial derivations are: \begin{align*} S\rightarrow LR\rightarrow DR\rightarrow a^2\\ S\rightarrow LR\rightarrow LDR\rightarrow DDR\rightarrow DaR\rightarrow a^2DR\rightarrow a^4 \end{align*} Hence, the number $$i$$ of D's produced with the rule $$L\rightarrow LD$$ determines which word $$a^{2^i}$$ is generated by the grammar.

How do you express the rule $$Da\rightarrow aaD$$ in terms of valid rules of CSG? I mean, rules like $$\alpha A\beta\rightarrow\alpha\psi\beta$$.

• When you want to ask a new question, use Ask Question, not Your Answer /Post Your Answer. Nov 10 at 8:55