# Why do derivation tree not make sense for context-sensitive grammars?

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.

• What don't you understand, exactly? They don't give a claim without reasoning. – Raphael Jul 7 '17 at 12:06
• Hint: Consider the Kuroda normal form; it's easier to see here what the issue is, compared to the prevalent definition of CSG. – Raphael Jul 7 '17 at 12:08
• I don;t understand why the author said that 'because they depend on the order of carrying out a derivation' which makes derivation trees don't make much sense for CSG. Does it mean that CFG derivation trees do not depend on the order of carrying out a derivation? – Blodstone Jul 7 '17 at 13:08

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.

1. 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*}

Consider the CFG $$S\to AB \qquad A \to a \qquad B \to b$$ Here, it does not matter if we consider the derivation $$S \to AB \to aB \to ab$$ or $$S \to AB \to Ab \to ab$$ The order of the expansion of the non terminals $A$ and $B$ is irrelevant. Because of that, we can represent this derivation as a tree, as if the non terminals $A,B$ were replaced in parallel.

This is not always the case for context sensitive grammars. $$S \to AB \qquad AB \to aB \qquad aB \to ab$$ clearly admits only one derivation $S \to^* ab$, and there we can not replace $B$ before $A$, since we can't rewrite the string in parallel ignoring the context of each non terminal, as we could for CFGs.