Write a grammar for a language $L=\{ba^{2^n}b |n\ge 1\}$ [closed]

Question

Write a grammar for a language $$L=\{ba^{2^n}b | n\ge 1\}.$$ It's not even context-free as I think. I just can't produce it, although I've tried a lot. Now my best attempt is: \begin{aligned} S &\to RLM \\ M &\to AM | A \\ LA &\to aa \\ aA &\to Aaa \\ RA &\to \varepsilon \end{aligned} But I've found example with deadlock $S→RLM→RLAAA→RaaAA→RaAaaA→RAaaaaA→aaaaA$

Answer 1

When designing a grammar you must have some idea what the productions are meant to do. You seem to have some good productions, but glued tegether in a unexplained way. What is $M$ doing in your grammar? It might generate any number of $a$'s if I am not mistaken.

The basic idea when generating stings of the form $a^{2^n}$ is indeed to have a symbol that moves over the string that duplicates every $a$. So

$aA \to Aaa$

is good as a basis for the grammar. Now add a starting production, that gives end-markers, which can be made to disappear and turn into $b$'s.

$S \to LaaR$

Now you finish. Make the $A$ appear so that it can move over the string to double the number of $a$'s, to get $La^4R$ etcetera.

Don't worry about "deadlock". That is sometimes hard to avoid if the grammar is not completely "synchronized". For instance if one side of the string wants to finish the derivation process, and the other side doesn't. Those derivations are discarded. What matters is that the strings that do have proper derivations are exactly those in $L$.