5
$\begingroup$

Is it possible to describe Context-free Tree Grammar $G_t$ such that set of yields of its trees will coincide with Context-sensitive word language $a^nb^nc^n$?

$\{a^nb^nc^n | n>0\}=\{Yield(t)|t\in L(G_t)\}$

I've tried to do it, using commonly used definition of CFTG (for instance see here), but I failed to express proper context-sensitive rules, using rules of the form $A(x_1,\dots,x_n)\rightarrow\alpha$. Looks like its description power is not enough, as I we can not operate subtrees structure in left side of the rule.

This question induced by well-known obvious relation between Regular Tree Grammars and Context-free word languages.

I would be happy if somebody would build such CFTG or confirm my assumption, that it is simply not possible.

UPD: More specifically, the problem is definition of variables inside rules: $A(x_1,\dots,x_n)\rightarrow\alpha$. It seems to be quite blur, as it is not quite clear: what are these variables? Can we say, that $x_i\in T_{\Sigma\cup X_n}$, where $X_n=\{x_1,\dots,x_n\}$, or not?

If we can describe CFTG rule as: $A(f(x))\rightarrow A_t(a, A(x))$, then problem goes away, it solves the question. But would it satisfy CFTG definition?

$\endgroup$
  • 2
    $\begingroup$ It's not possible, CFTG generate indexed languages as yield languages (en.wikipedia.org/wiki/Indexed_language), a strict subclass of CSL. $\endgroup$ – Sylvain Jan 23 '17 at 6:44
  • $\begingroup$ The essential question is: can we use such kind of rules as $A(f(x))\rightarrow A_t(a, A(x))$ or not. $\endgroup$ – Andrey Lebedev Jan 23 '17 at 22:01
  • 1
    $\begingroup$ @Sylvain, it looks like I'm confused now. The language $a^nb^nc^n$ is actually indexed language, hence it should be possible describe corresponsing CFTG $\endgroup$ – Andrey Lebedev Jan 23 '17 at 22:02
  • $\begingroup$ seems like I read your question too fast: I thought you were asking whether CFTGs can generate any CSL. For the particular language $\{a^nb^nc^n\mid n>0\}$ you mention at the beginning of your question, it's the very first example in Fischer's paper (Grammars with macro-like productions. In SWAT’68, pages 131–142. dx.doi.org/10.1109/SWAT.1968.12.) $\endgroup$ – Sylvain Jan 24 '17 at 18:35
1
$\begingroup$

After a couple of hours of thinking I found at least proper form of grammar. Thanks to @Sylvain's commentary and link to Fisher's paper, which given me a clue.

Proper context-free tree grammar, which yield language coincides with $\{a^nb^nc^n|n>0\} $ will have simplest form:

$G=\{\Sigma,N,S,P\}$, where $\Sigma=\{a,b,c\}$, $N=\{S_t,F,A,B,C\}$, $S=\{S_t\}$, and set of production rules:

$S_t\rightarrow F(a,b,c)\\ F(x_1,x_2,x_3)\rightarrow F(A(a,x_1),B(b,x_2),C(c,x_3))$

That is it. Core idea is to wrap "stack" into subtrees of the form $A(a,x_1)$.

Thereby we receive following productions:

  1. $S_t\Rightarrow F(a,b,c)$, $yield(F(a,b,c))=abc$
  2. $S_t\Rightarrow F(a,b,c)\Rightarrow F(A(a,a),B(b,b),C(c,c))$, $yield(F(A(a,a),B(b,b),C(c,c)))=aabbcc$
  3. $S_t\Rightarrow F(a,b,c)\Rightarrow F(A(a,a),B(b,b),C(c,c))\Rightarrow F(A(a,A(a,a)),B(b,B(b,b)),C(c,C(c,c)))$,
  4. and so on.
$\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.