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.
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
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP