# Example of context-free tree language which can not be generated by monadic CFTG

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.

• 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. – Andrey Lebedev Jun 26 '18 at 9:56
• 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$ – Andrey Lebedev Jun 29 '18 at 5:50
• 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! – Andrey Lebedev Jun 29 '18 at 9:24
• @MichaelWehar this already has been examined: aclweb.org/anthology/C04-1012 – Andrey Lebedev Jul 3 '18 at 9:21
• 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. – Andrey Lebedev Jul 3 '18 at 14:12

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.

• 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. :) – Michael Wehar Jul 3 '18 at 16:33