<p>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 <em>no</em> symbol from $f(A\rightarrow x)$ appears in $uw$.</p>

<p>$\{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 <em>allow</em> the  nonterminals of some type to double, but we can't <em>force</em> it.</p>

<blockquote>
  <p>It seems obvious to me that one can't get <em>more</em> 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?</p>
  
  <p>I'm also interested in superexponential growth in forbidding languages
  (e.g. is $\{a^{2^{2^n}} : n \in \mathbb{N}\}$ an RFCL).</p>
</blockquote>

CC BY-SA 3.0
2012-02-29T16:30:22.060Z
It might be helpful to link to, or provide inline, a definition of "permitting context"
Suresh Venkat
CC BY-SA 3.0
2012-03-01T12:13:59.663Z
@SureshVenkat: good idea, done.
Max
CC BY-SA 3.0
2012-03-01T16:37:35.140Z
What does "random" mean in this context ?
Suresh Venkat
CC BY-SA 3.0
2012-03-02T10:01:36.513Z
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
CC BY-SA 4.0
2019-01-13T23:09:33.370Z
A (not too) recent overview on regulated rewriting is here: Dassow, Jürgen, [http://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.
Hermann Gruber
<fl.formal-languages>
Is $\{a^n b^m : 1 \le m \le 2^{2^n}\}$ a permitting-context language?
Max
# Is $\{a^n b^m : 1 \le m \le 2^{2^n}\}$ a permitting-context language?

(Asked by: username_0 on 2012-02-29)

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

**Tags:** fl.formal-languages

> **Comments:**
> **username_1**: It might be helpful to link to, or provide inline, a definition of "permitting context"  
> **username_0**: @SureshVenkat: good idea, done.  
> **username_1**: What does "random" mean in this context ?  
> **username_0**: 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.  
> **username_2**: A (not too) recent overview on regulated rewriting is here: Dassow, Jürgen, [http://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.  

---

## 0 answers

