A random permitting-context grammar is a context-free grammar $(N, \Sigma, P, S)$ equipped with a function $p : P \rightarrow 2^N$. The rule $A \rightarrow x$ can be applied to $uAw \Rightarrow uxw$ if every symbol in $p(A\rightarrow x)$ appears in $uw$. A forbidding-context grammar is similar, except equipped with a function $f : P \rightarrow 2^N$, and a rule application is allowed if no symbol from $f(A\rightarrow x)$ appears in $uw$.

$\{a^n b^m : 1 \le m \le 2^n\}$ is a random permitting-context language (RPCL), though $\{a^n b^m : m = 2^n\}$ is not (as can be proved by Ewert and Van der Walt's pumping lemma for RPCLs). In a permitting grammar we can allow the nonterminals of some type to double, but we can't force it.

It seems obvious to me that one can't get more than exponential growth, but I can't see how to prove it (the pumping lemma certainly doesn't help, since it will just increase the number of $a$'s). Is there a known result that helps here?

I'm also interested in superexponential growth in forbidding languages (e.g. is $\{a^{2^{2^n}} : n \in \mathbb{N}\}$ an RFCL).

  • 4
    $\begingroup$ It might be helpful to link to, or provide inline, a definition of "permitting context" $\endgroup$ – Suresh Venkat Feb 29 '12 at 16:30
  • $\begingroup$ @SureshVenkat: good idea, done. $\endgroup$ – Max Mar 1 '12 at 12:13
  • 1
    $\begingroup$ What does "random" mean in this context ? $\endgroup$ – Suresh Venkat Mar 1 '12 at 16:37
  • 1
    $\begingroup$ The idea is that the context could appear at "any random position", rather than adjacent as in a CSG. However, it seems to me that "global" would have been a better choice. $\endgroup$ – Max Mar 2 '12 at 10:01
  • $\begingroup$ A (not too) recent overview on regulated rewriting is here: Dassow, Jürgen, [theo.cs.uni-magdeburg.de/dassow/tarraphd.pdf ''Grammars with Regulated Rewriting'']. Lecture in the 5th PhD Program "Formal Languages and Applications", Tarragona, Spain, 2006. $\endgroup$ – Hermann Gruber Jan 13 '19 at 23:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.