construction of a^(2^i) language grammar

Question

I'm kind a stuck with automaton and grammars problem. I've searched a lot but without any success.

Is it even possible to construct a grammar generating this language L?

 L = { a(2i) | i >= 0} 

Can anyone provide me with simple solution?

Answer 1

It's certainly possible to write a grammar for this language, but it won't be a context-free grammar. That's easy to demonstrate using the pumping lemma.

The pumping lemma states that for any CFL, there is some integer p such that any string s in the language whose length is at least p can be written as uvxyz, where u, v, x, y and z are strings and vy is not empty, and for all integers n, the string uvnxynz is also in the language.

That is, for any string in the language (whose length l is greater than p), there is there some k such that there are strings in the language whose lengths are l + nk for any integer n. That is not the case for the language a2i, since those strings have exponential lengths, so the language cannot be context-free.

Constructing a non-context-free grammar for the language is not that difficult, but I don't know how useful it is.

The following is a Type 0 grammar (i.e. it's not context-sensitive either), but only because of the productions used to get rid of the metacharacters. The basic idea here is that there we put start and end markers around the string ([ and ]) and we have a "duplicator" (↣) which moves from left to right doubling the a's; when it hits the end marker, it either turns into a back-shuttle (↢) or it eats the end-marker and turns into a start-marker-destroyer (↞)

Start: [↣a]
↣a: aa↣
↣]: ↢]
↣]: ↞
a↢: ↢a
a↞: ↞a
[↢: [↣
[↞: