I need to define a grammar for $L=\{a^ib^ic^jd^j| i \ge j \ge 0\}$ as I wasn't told about any restrictions for the grammar, e.g context-free or context-sensitive, I assume any derivation rules can be used here.
Because the number of $a$s and $b$s is greater than, or equals to, the number of $c$s and $d$s I have this first set of rules $$ S \rightarrow \varepsilon | AS | ASD $$ now I have a series of $A$s and $D$s and I'm looking for a way to derive the desired words from this series. I came up with these rules $$ AD \rightarrow abcd \\ aAb \rightarrow aabb \\ Aa \rightarrow aA \\ cDd \rightarrow ccdd \\ dD \rightarrow Dd $$ with which I can get for example $$ S\Longrightarrow AS \Longrightarrow AASD \Longrightarrow AAASDD \Longrightarrow AAADD \\ \Longrightarrow AAabcdD \Longrightarrow AaAbcdD \Longrightarrow AaabbcdD \Longrightarrow aAabbcdD \\ \Longrightarrow aaAbbcdD \Longrightarrow aaabbbcdD \Longrightarrow aaabbbcDd \Longrightarrow aaabbbccdd \in L $$
As pointed out by Nathaniel's comment the word $ab\in L$ isn't derived from my proposed grammar, so I've revised my derivation rules $$ S \rightarrow \varepsilon | ABR | ABRCD \\ R \rightarrow \varepsilon | BR | BRC \\ AB \rightarrow ab \\ bB \rightarrow Bb \\ aBb \rightarrow aabb \\ CD \rightarrow cd \\ Cc \rightarrow cC \\ cCd \rightarrow ccdd \\ $$ Now I've $A$ and $D$ as place holders for the beginning and the ending of the string so I know where to insert the initial $ab$ and $cd$ and then I move the $B$s one by one to be in the context of $a$ and $b$ to replace them with $ab$ (the same for $C$s)
Is this a valid grammar for $L$, i.e can I have derivation rules of the form $XY\rightarrow YX$ (so far I've only worked with context-free or context-sensitive grammars so I'm not sure to what extent can I go with derivation rules of unrestricted grammar)? If not how can a define a grammar for this type of language? And If it is, is there a better grammar than the one above?
