6
$\begingroup$

Assuming that a context-free tree language (CFTL) is that which is generated by a context-free tree grammar (CFTG), I am looking for an example of CFTL which can not be generated by a monadic CFTG (MCFTG).

In other words, I am looking for such a non-monadic CFTG for which it is not possible to construct an equivalent (MCFTG).

The all examples of CFTG's which exist in papers are essentially monadic CFTG.

I am still trying to build such a grammar by myself. But may be somebody already knows such an example and could share it as an answer. I deeply appreciate any help.

$\endgroup$
13
  • $\begingroup$ The answer should provide an example of CFTG for which it is not possible to construct a monodic CFTG (a CFTG where rank of all non-terminals is 0 or 1) which produces the same tree language. $\endgroup$ Jun 26, 2018 at 9:56
  • 1
    $\begingroup$ Cool, thanks @MichaelWehar! However I have a feeling that the following MCFGT will produce the same tree language, could you please verify it? $S\rightarrow C(b(a,a))$, $C(x)\rightarrow C(b(x,x))$, $C(x)\rightarrow x$ $\endgroup$ Jun 29, 2018 at 5:50
  • 1
    $\begingroup$ However, if you change your example to: $S\rightarrow T(a,a)$, $T(x_1,x_2)\rightarrow T(b(x_1,x_2),c(x_1,x_2)$, $T(x_1,x_2)\rightarrow a(x_1,x_2)$ - this grammar seems to be an answer! $\endgroup$ Jun 29, 2018 at 9:24
  • 1
    $\begingroup$ @MichaelWehar this already has been examined: aclweb.org/anthology/C04-1012 $\endgroup$ Jul 3, 2018 at 9:21
  • 1
    $\begingroup$ Not actually. The string language is (aa)^(2n), it can be generated by your first version of CFTG which has an equivalent MCFTG. However the tree language is different, and it has nothing to do with TAG. $\endgroup$ Jul 3, 2018 at 14:12

1 Answer 1

1
$\begingroup$

Based on the comment of Michael Wehar, I've found this grammar to be that one which doesn't have an equivalent MCFTG:

$S\rightarrow T(a,a)$

$T(x_1,x_2)\rightarrow T(b(x_1,x_2),c(x_1,x_2))$

$T(x_1,x_2)\rightarrow a(x_1,x_2)$

This grammar produces perfect binary trees where in each branch the left child has a label a if it is a leaf, and has a label b otherwise; the right child has a label a if it is a leaf, and has a label c otherwise.

I don't have a very rigorous proof of this fact, however here below there are some observations.

It makes it impossible to build such a monodic context free tree grammar which will produce the same language of trees. This is because any single-ranked non-terminal can not properly set a parent node label (b or c). This label depends on "context": a knowledge about wether this node is left or wether it is right.

Also, because the depth of each path in the given tree is the same, it can not be produced by a grammar where each next branch is generated by an independent non-terminal.

$\endgroup$
1
  • 1
    $\begingroup$ You gave a really great description of the tree language recognized by your grammar!! I'm going to think about your explanation and see if I can turn it into a rigorous proof. :) $\endgroup$ Jul 3, 2018 at 16:33

Your Answer

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

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