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

  • $\begingroup$ 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. $\endgroup$
    – Berci
    May 7, 2018 at 21:28
  • $\begingroup$ 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 $\endgroup$ May 7, 2018 at 21:32
  • $\begingroup$ 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? $\endgroup$
    – Berci
    May 7, 2018 at 21:35
  • $\begingroup$ Yes, it's important. Grammar have to generate only words from language $\endgroup$ May 7, 2018 at 21:37
  • $\begingroup$ 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. $\endgroup$
    – Berci
    May 7, 2018 at 21:48

1 Answer 1


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .