TransWikia.com

Context free languages invariant by "shuffling" right hand side

Computer Science Asked by Vor on December 10, 2021

Given a grammar $G$ for a Context Free language $L$, we can augment it by "shuffling" 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 -> XA | YB         S -> XA | AX | YB | BY
A -> YS | SY         A -> YS | SY
B -> XS | SX         B -> XS | SX
X -> 1               X -> 1
Y -> 0               Y -> 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 "shuffle invariance" of grammars also corresponds to a class of languages.

One Answer

Your theorem doesn't hold.

Consider the grammar

$$ begin{align} &S to 1T mid T1 \ &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.

Answered by Yuval Filmus on December 10, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP