I don't understand the line in the paper Mappings and Grammars on Trees by William C. Rounds, the passage:Transformational theory, as developed by Chomsky  [7] and many others, deals with the notion of phrase-structure grammar, and with certain mappings defined on derivation trees associated with the grammar. Derivation trees do not make much sense for context-sensitive grammars, because they depend on the order of carrying out a derivation. We will therefore assume that mappings are to be defined on context-free derivation trees. Thank you.
Why do derivation tree not make sense for context-sensitive grammars?
formal languages;formal grammars;context sensitive
For context-free grammars, the order in which you execute rules does not matter. Formally, let$\qquad \gamma = w_1 A_1 w_2 \dots w_{n-1} A_{n-1} w_n$with $A_i \in N$ and $w_i \in T^*$ for all $i$. Then, any order of applying rules $A_i \to \alpha_i$ yields the same sentential form. Thus, it makes sense to identify $\gamma$ with a level in a syntax tree -- the children of all the nodes (if any) are independent of each other.For context-sensitive grammars, this is not true. Consider this grammar:$\qquad\begin{align*} S\ \ &\to AS \mid A \\ AS &\to a \\ SA &\to b \\ A\ \ \ &\to c \end{align*}$Observe how the set of applicable rules changes as soon as you start applying them! Therefore, while you can still imagine a tree structure here, the children are no longer independent. Also, you'd have to connect two nodes from higher levels each node -- and arbitrarily many for general CSGs. Since any symbol may influence the picking of many rules, this will give you a DAG, but no tree.As has been aptly noted by commentes chi and fade2black, this grammar is not context-sensitive in the strict sense of the definition. I find it clearer to illustrate the issue; but still, this is a clearly context-sensitive variant:$\qquad\begin{align*}  S\ \ &\to AS \mid AB \\  AS &\to CC \\  SA &\to DD \\  A\ \ \ &\to c \\  B \ \ \ &\to d \\   C \ \ \ &\to a \\  D \ \ \ &\to b\end{align*}$