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

93 Views Asked by At

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

1

There are 1 best solutions below

0
On BEST ANSWER

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