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$
$\endgroup$
7
-
$\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$– BerciMay 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$– ioleg19029700May 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$– BerciMay 7, 2018 at 21:35
-
$\begingroup$ Yes, it's important. Grammar have to generate only words from language $\endgroup$– ioleg19029700May 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$– BerciMay 7, 2018 at 21:48
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
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}$$
