Context free languages invariant by "shuffling" right hand side Given a grammar $G$ for a Context Free language $L$, we can augment it by &quot;shuffling&quot; the right hand side of each production, e.g.:
$A \to BCD$ is expanded to $A \to BCD \; | \; BDC \; | \; CBD \; | CDB \; | \; DBC \; | \; DCB$
It may happen that the resulting language $L'$ generated by the expanded $G'$ is equal to $L$
For example:
Source               Shuffled
S -&gt; XA | YB         S -&gt; XA | AX | YB | BY
A -&gt; YS | SY         A -&gt; YS | SY
B -&gt; XS | SX         B -&gt; XS | SX
X -&gt; 1               X -&gt; 1
Y -&gt; 0               Y -&gt; 0


Is there a name for such class of grammars ($L(G) = L(G_{\text{shuffled}}))$?


Furthermore, does this theorem hold?

Theorem [it doesn't hold, see Yuval's answer and comments]: If exists a grammar $G$ such that, $L(G) = L(G_{\text{shuffled}})$, then for all $G'$ such that $L(G) = L(G')$ we have $L(G') = L(G'_{\text{shuffled}})$
In other words the &quot;shuffle invariance&quot; of grammars also corresponds to a class of languages.
Your theorem doesn't hold.
Consider the grammar
$$
\begin{align}
&amp;S \to 1T \mid T1 \\
&amp;T \to 23 \mid 32 \\
\end{align}
$$
Shuffling the grammar results in the same language.
Now consider instead the grammar
$$
S \to 123 \mid 132 \mid 231 \mid 321
$$
which generates the same language.
Shuffling this grammar results in a larger language.