4
$\begingroup$

Consider arbitrary context-sensitive grammar on strings $G_s$.

Is any known and described formalism (or type) for tree grammars, using which we can build weak-equivalent tree grammar $G_t$, which yield language will coincide with $L(G_s)$:

$L(G_s)=\{yield(t)|t\in L(G_t)\}$ ?

Yield operator is as it defined in TATA book: it computes a word from a tree by concatenating the leaves of the tree from the left to the right.

It is known, for instance, that for indexed grammars, context-free tree grammars have weak-equivalence to them in sense of strings language. Same property exists between regular tree grammars and context-free word grammars.

$\endgroup$
  • $\begingroup$ The derivation process of CS-grammars has no tree structure at all. That suggests that such a connection is very improbable. Unfortunately I do not know how to make this into a formal answer. $\endgroup$ – Hendrik Jan Jan 29 '17 at 15:21
  • $\begingroup$ Dear @HendrikJan, It doesn't matter that derivation process for CS-grammars has no tree structure. I'm talking about yield languages, what is set of strings, composed from leaves of trees (see my update please). Exactly in this sense we can talk about weak equivalence. $\endgroup$ – Andrey Lebedev Jan 29 '17 at 15:33

Your Answer

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

Browse other questions tagged or ask your own question.