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$

  • $\begingroup$ What kind of grammar are you looking for? $\endgroup$ – Yuval Filmus May 7 '18 at 20:01
  • $\begingroup$ Any. There can be even rules like S-->SS $\endgroup$ – ioleg19029700 May 7 '18 at 20:05
  • 1
    $\begingroup$ Context-sensitive grammar? Unrestricted grammar? What's the context and motivation for this problem? Why is it interesting? Where did you encounter it? Unrestricted grammars can generate any r.e. language, so if you know how to make a Turing machine to recognize the language, then you can mechanically apply the proof of that fact to construct an unrestricted grammar for it. This is possible and straightforward but doesn't seem very enlightening or interesting or fun; rather it seems tedious and pointless. $\endgroup$ – D.W. May 7 '18 at 20:16
  • 1
    $\begingroup$ Cross-posted: cs.stackexchange.com/q/91614/755, math.stackexchange.com/q/2771255/14578. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. May 8 '18 at 1:32
  • 1
    $\begingroup$ I'm voting to close this question because it was cross-posted on Math.SE. $\endgroup$ – D.W. May 8 '18 at 1:33

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

| cite | improve this answer | |
  • $\begingroup$ Could you please comment about "deadlock" terminology? I thought it is non-terminating derivation, which is, as you said, discarded. $\endgroup$ – Evil May 8 '18 at 2:25
  • 1
    $\begingroup$ @Evil Yes, I think it is just that. The terminology seems totally nonstandard, that's why I added quotes. $\endgroup$ – Hendrik Jan May 8 '18 at 7:55

Not the answer you're looking for? Browse other questions tagged or ask your own question.