Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
It might be helpful to link to, or provide inline, a definition of "permitting context" – Suresh Venkat Feb 29 '12 at 16:30
@SureshVenkat: good idea, done. – Max Mar 1 '12 at 12:13
What does "random" mean in this context ? – Suresh Venkat Mar 1 '12 at 16:37
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. – Max Mar 2 '12 at 10:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.