<p>Using the method in <a href="https://cstheory.stackexchange.com/questions/4962/do-there-exists-polynomial-size-cfg-that-describe-this-finite-language/4969#4969">this answer</a> one can show that the smallest context-free grammar for all permutation of $n$ symbols has exponential size in $n$.</p>

CC BY-SA 3.0
2011-05-13T05:06:08.767Z
2011-05-13T05:06:08.767Z
2017-04-13T12:32:28.080Z
Yuval Filmus
<p>This may sound like theoretically void question, because certainly permutation is expressible even on the lowest level of Chomsky hierarchy:</p>

<pre><code>P -&gt; a b c
  |  a c b
  |  b a c
  |  b c a
  |  c a b
  |  c b a
</code></pre>

<p>In practice, however, proposition that the only way to describe SQL syntax is permuting "<em>where</em>", "<em>group by</em>", "<em>having</em>" (and many more similar clauses in some SQL dialects) is silly.</p>

<p>Boolean grammars allow succinct expression for permutation </p>

<pre><code>X -&gt; a
   | b
   | c

Y -&gt; 
   | X

P -&gt; X X X &amp; - Y a Y a Y &amp; - Y b Y b Y &amp; - Y c Y c Y
</code></pre>

<p>but perhaps there is a way to do it in the context free realm too?  </p>

CC BY-SA 3.0
2011-05-12T23:03:12.537Z
For any finite language, if you just iterate over all the member you could express it as a regular language. The problem is with infinite languages, and this is where we need patterns and higher level in the Chomsky hierarchy. Is your question is how to express permutations of an infinite set of symbols in a context free grammar ?
Mohammad Alaggan
CC BY-SA 3.0
2011-05-12T23:23:27.153Z
Let scope it to finite set of symbols and require a grammar of the size proportional (or growing moderately) with the number of terminals.
Tegiri Nenashi
CC BY-SA 3.0
2011-05-13T13:27:24.467Z
The complement is easily expressed as e.g. $S \rightarrow AaAaA, A \rightarrow aA | \epsilon$ for all $a \in \Sigma$.
Raphael
CC BY-SA 3.0
2011-05-13T17:57:52.553Z
@Raphael: The complement should also include all "subpermutations". In particular, we could intersect it with the regular language $(A \setminus a)^{|A|-1}$ to get all permutations on $A \setminus a$, along with some "extras".
Yuval Filmus
CC BY-SA 3.0
2011-05-13T19:58:53.933Z
Yuval, I intended to build the complement of $\{ w_1\dots w_n \in \Sigma^* \mid i \neq j \leadsto w_i \neq w_j\}$, that is I considered the set of all permutations to include all permutations of subsets of the alphabet.
Raphael
<fl.formal-languages>
compact context free expression for permutation
Tegiri Nenashi
# compact context free expression for permutation

(Asked by: username_0 on 2011-05-12)

This may sound like theoretically void question, because certainly permutation is expressible even on the lowest level of Chomsky hierarchy:
P -> a b c
  |  a c b
  |  b a c
  |  b c a
  |  c a b
  |  c b a

In practice, however, proposition that the only way to describe SQL syntax is permuting "where", "group by", "having" (and many more similar clauses in some SQL dialects) is silly.
Boolean grammars allow succinct expression for permutation 
X -> a
   | b
   | c

Y -> 
   | X

P -> X X X & - Y a Y a Y & - Y b Y b Y & - Y c Y c Y

but perhaps there is a way to do it in the context free realm too?

**Tags:** fl.formal-languages

> **Comments:**
> **username_1**: For any finite language, if you just iterate over all the member you could express it as a regular language. The problem is with infinite languages, and this is where we need patterns and higher level in the Chomsky hierarchy. Is your question is how to express permutations of an infinite set of symbols in a context free grammar ?  
> **username_0**: Let scope it to finite set of symbols and require a grammar of the size proportional (or growing moderately) with the number of terminals.  
> **username_2**: The complement is easily expressed as e.g. $S \rightarrow AaAaA, A \rightarrow aA | \epsilon$ for all $a \in \Sigma$.  
> **username_3**: @username_2: The complement should also include all "subpermutations". In particular, we could intersect it with the regular language $(A \setminus a)^{|A|-1}$ to get all permutations on $A \setminus a$, along with some "extras".  
> **username_2**: Yuval, I intended to build the complement of $\{ w_1\dots w_n \in \Sigma^* \mid i \neq j \leadsto w_i \neq w_j\}$, that is I considered the set of all permutations to include all permutations of subsets of the alphabet.  

---

## 1 answers

### Answer by username_3 on 2011-05-13. Score: 7 | Accepted answer

Using the method in [this answer](https://cstheory.stackexchange.com/questions/4962/do-there-exists-polynomial-size-cfg-that-describe-this-finite-language/4969#4969) one can show that the smallest context-free grammar for all permutation of $n$ symbols has exponential size in $n$.


---

