# Unrestricted grammar for the language of strings whose length is not $2^n$

The following exercise is inspired by an old exam question (note that this is not the question):

Let us define a single-letter alphabet $\Sigma = \{a\}$ and the language $L = \{ w \in \Sigma^*: |w| = 2^n, n \in \mathbb Z_+\}$. (In other words, $L = \{a^2, a^4, a^8, \ldots \}$.) What is an unrestricted grammar for $L$?

I thought of a solution using binary number representation. Consider the grammar:

$S \rightarrow 10TaX$
$T \rightarrow 0T | \epsilon$
$0a \rightarrow aa0$
$0X \rightarrow X$
$1a \rightarrow a1$
$1X \rightarrow \epsilon$

$\epsilon$ signifies the empty string. Using the first two production rules, we can produce a string of the type $10^naX$, for example $100aX$. One route here to get rid of the non-terminal symbols is $100aX \Rightarrow 10aa0X \Rightarrow 1aa0a0X \Rightarrow 1aaaa00X \Rightarrow 1aaaa0X$ $\Rightarrow 1aaaaX \Rightarrow \ldots \Rightarrow aaaa1X \Rightarrow aaaa = a^4$.

Assuming that this solution is correct, one interesting thing about it is that by modifying the third production rule to $0a \rightarrow a^k0$ one can get a restriction-free grammar for strings of length $k^n$ instead. But maybe there is a cleaner solution, so I am interested in seeing other examples of unrestricted grammars for the language.

However, here comes the actual question: the existence of an unrestricted grammar for $L$ only proves that it is recursively enumerable. Therefore I would like to ask for an unrestricted grammar of $\overline{L}$ (then we have one proof that $L$ is a Turing-decidable language).

• Can you edit the question to be clearer about what specifically your question is? It sounds like your question is "are there other examples of unrestricted grammars for the language?", but the answer to that is a trivial and boring "yes" (for instance, replace the rule $1X \to \epsilon$ with the two rules $1X \to Y$ and $Y \to \epsilon$), so I suspect that's not really what you mean to ask. Maybe you can identify some sense in which the solution you have is not satisfactory, and then ask "is there an unrestricted grammar that has property P?", where you specify what P is.
– D.W.
Oct 30 '15 at 21:53
• Also, it's usually preferable to ask only one question per question, if possible. It sounds like you have two questions "is there another grammar for $L$?" and "is there a grammar for $\overline{L}$?". While those are indeed related, when someone posts an answer that answers one of those two questions but not the other, the situation is a bit less than ideal -- now the question gets marked as answered. Not a disaster, certainly, but it illustrates that the Stack Exchange software/format might work a bit better when you have one question per question. Just trying to help you get good answers.
– D.W.
Oct 30 '15 at 21:56
• Thanks @D.W. My question is really threefold; (i) is the unrestricted grammar that I posted correct? (ii) do there exists better examples than the one I posted? (iii) what is a restriction-free grammar for the complement of L?. But of those questions, I am mostly interested in (iii) and the discussion leading up to it mostly intended for background information.
– Sid
Oct 30 '15 at 22:13
• At minimum, I suggest editing the question to include that information in the question. (As a side note, "please check whether my solution is correct" questions are usually discouraged here,as only "yes/no" answers are possible, which won't help you or future visitors. See here and here.)
– D.W.
Oct 30 '15 at 22:17
• @D.W. That is very understandable.
– Sid
Oct 30 '15 at 22:26

1. Your method is correct to generate $L$. But if you change the rule to $0a \to a^k0$ then the language you generate is $L^{'}=\{a^k,a^{k^2},a^{k^3}....\}$ ( $k >2$) .
2. You can show that language $L$ is indeed decidable. One way is to give an algorithm that halts on every input in $\sum^{*}$ and gives the correct result. Following is the approach
(1) If the input is empty reject.
(2) If not empty , check if there are even number of 'a' or odd. If only one 'a' is there accept. If odd 'a' ( > 1 ) are there reject.
(3) If even 'a' are there, go back to starting of input and cross off alternate 'a' from beginning to end of input. Go back to step (2).
The algorithm accepts the string $a$ in addition. You can always modify the above algorithm, keeping a special check that if the input is 'a' reject.
• Thank you for your answer. Your point in 1 is absolutely true; what I wrote in my question was a typo. But I am not really interested in a general algorithm for proving that L is decidable, what I would like to see is a restriction-free grammar for the complement of L (whose existence has the nice consequence of proving that L is decidable).
– Sid
Oct 30 '15 at 22:17
• @Sid I found this link : cs.stackexchange.com/questions/6504/… . Not exactly what you are looking for. But one you have a Turing machine that decides a language , you can construct a one that decides its complement and then convert it to unrestricted grammar using the link. I am not sure but the unrestricted grammar for $\overline{L}$ would not be that neat. Hope it helps. Oct 30 '15 at 22:34

As I show here by giving a context-sensitive grammar for $L$, it is actually in CSL. Since CSL is closed against complementation, this answers your question.

• What question does this answer? In your link, I do not see an unrestricted grammar for the complement of L.
– Sid
Oct 31 '15 at 18:23
• @Sid, the answer proves that there exists a CSL grammar for the complement of L (and thus that there exists an unrestricted grammar). That seems to answer the question marked as "the actual question" in your question.
– D.W.
Nov 1 '15 at 2:04
• No, this is not what I wanted. What I wrote there explicitly is "Therefore I would like to ask for an unrestricted grammar of L". I don't want a proof that it exists, I want to see an actual example of it.
– Sid
Nov 1 '15 at 4:36
• @D.W. And also, if that was not clear enough (which it is), I also wrote the following in our discussion in the comments: "(iii) what is a restriction-free grammar for the complement of L? But of those questions, I am mostly interested in (iii) and the discussion leading up to it mostly intended for background information." So while I acknowledge that it may be difficult to answer my question, an answer that would try to do so and/or give an argument why this is a difficult would get an "accepted answer" from me.
– Sid
Nov 1 '15 at 4:42
• @Sid Use the constructions from the closure property proofs. That is, a) transform the grammar into an LBA, b) apply the construction used to prove that CSL is closed against complement, and c) re-transform the LBA into a CSG. Since following this route is pretty much routine, it's not worth writing it out at length (unless you really need the resulting grammar, which I for one don't); the "hard" part was finding a grammar to start with, which I did for you over at that other answer.
– Raphael
Nov 1 '15 at 10:09