5
$\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.

Improve this question
$\endgroup$
2
  • $\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, 2017 at 15:21
  • 1
    $\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, 2017 at 15:33

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.