1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What don't you understand, exactly? They don't give a claim without reasoning. $\endgroup$ – Raphael Jul 7 '17 at 12:06
  • 1
    $\begingroup$ Hint: Consider the Kuroda normal form; it's easier to see here what the issue is, compared to the prevalent definition of CSG. $\endgroup$ – Raphael Jul 7 '17 at 12:08
  • $\begingroup$ 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? $\endgroup$ – Blodstone Jul 7 '17 at 13:08
3
$\begingroup$

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*}$

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.