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?

Improve this question
$\endgroup$
4
  • 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, 2017 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, 2017 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, 2017 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, 2017 at 18:35

1 Answer 1

Reset to default
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.
Improve this answer
$\endgroup$

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.

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