# Write grammar for language $L=\bigl\{ba^{2^n}b \mid n\ge 1\bigr\}$

Write grammar for language $L=\{ba^{2^n}b | n\ge 1\}$. It can be grammar of any type without any restriction on rules look. 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\to RLM\to RLAAA\to RaaAA \to RaAaaA \to RAaaaaA \to aaaaA$
So I'm stuck

• Exactly what can be the rules? I guess, something like ^$wA\to ww$ is not allowed, where $w$ is general/varying, i.e. does not denote a specific word, and ^ denotes the beginning. May 7, 2018 at 21:28
• Rules doesn't have any restrictions on their left and right parts, but you have to use non-terminal and symbols a,b in any combinations May 7, 2018 at 21:32
• And, is it important to reach a 'leaf' of only non-terminals for every possible deduction branch? Can't we just say, that this branch doesn't produce any word for the language? May 7, 2018 at 21:35
• Yes, it's important. Grammar have to generate only words from language May 7, 2018 at 21:37
• From en.wikipedia.org/wiki/Formal_grammar, it seems there's no such explicit requirement in the definition of grammar. Also, "the language of G, denoted as L(G), is defined as all those sentences that can be derived in a finite number of steps from the start symbol S" -- this allows having deadlock deductions, those simply lead to nowhere. May 7, 2018 at 21:48

A simplified version of this answer, relying on the exact same idea for the language $\{a^{2^n}\mid n\ge1\}$ is \begin{align} S&\to BXAE\\ XA&\to AAX\\ XE&\to YE\,|\,F\\ AY&\to YA \\ BY&\to BX\\ AF&\to FA\\ BF&\to \varepsilon\\ A&\to a\end{align}