<p>Based on the comment of <a href="https://cstheory.stackexchange.com/users/14207/michael-wehar">Michael Wehar</a>, I've found this grammar to be that one which doesn't have an equivalent MCFTG:</p>

<p>$S\rightarrow T(a,a)$</p>

<p>$T(x_1,x_2)\rightarrow T(b(x_1,x_2),c(x_1,x_2))$</p>

<p>$T(x_1,x_2)\rightarrow a(x_1,x_2)$</p>

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

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

<p>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 (<code>b</code> or <code>c</code>). This label depends on "context": a knowledge about wether this node is left or wether it is right. </p>

<p>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.</p>

CC BY-SA 4.0
2018-07-03T16:33:32.793Z
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
CC BY-SA 4.0
2018-07-03T14:03:56.613Z
2018-07-03T14:03:56.613Z
Andrey Lebedev
<p>Assuming that a <em>context-free tree language</em> (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).</p>

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

<p>The all examples of CFTG's which exist in papers are essentially monadic CFTG. </p>

<p>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.</p>

CC BY-SA 4.0
2018-06-26T09:56:42.053Z
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
CC BY-SA 4.0
2018-06-29T05:33:19.290Z
Consider the following CFTG.  Symbols: S has arity 0, T has arity 2, a has arity 0, and b has arity 2.  Grammar Rules: S() -> T(a, a), T(x, y) -> T(b(x, y), b(x, y)), T(x, y) -> b(x, y)
Michael Wehar
CC BY-SA 4.0
2018-06-29T05:38:00.473Z
I don't have a proof that it does not have an equivalent MCFTG.  I just suspect that it might not have an equivalent MCFTG.  Please correct me if I'm wrong.  :)
Michael Wehar
CC BY-SA 4.0
2018-06-29T05:50:03.603Z
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
CC BY-SA 4.0
2018-06-29T09:24:52.943Z
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
CC BY-SA 4.0
2018-06-29T17:16:23.387Z
Wow!!  Yes, you're right, there is an equivalent MCFTG to my grammar.  Let me think about yours.  :)
Michael Wehar
CC BY-SA 4.0
2018-07-03T06:37:36.600Z
I thought about your grammar trying to see if I could find an equivalent MCFGT, but I wasn't able to come up with one.  This almost looks like an equivalent grammar: $S \rightarrow a(T_1, T_2)$, $T_1 \rightarrow b(T_1, T_2)$, $T_2 \rightarrow c(T_1, T_2)$, $T_1 \rightarrow a$, $T_2 \rightarrow a$
Michael Wehar
CC BY-SA 4.0
2018-07-03T06:38:28.943Z
The reason that this does not work is because this grammar could generate a tree that is not balanced while your grammar only generates balanced trees.
Michael Wehar
CC BY-SA 4.0
2018-07-03T06:40:39.480Z
That's exactly an idea to generated balanced trees with different labels in the left and right sides. Such a grammar seems to be not having an equivalent MCFTG!
Andrey Lebedev
CC BY-SA 4.0
2018-07-03T06:50:45.867Z
I haven't yet come up with a proof for why your grammar has no equivalent MCFTG.  If it does not have an equivalent MCFTG, then I suspect we would be able to prove something much more general about the restrictiveness of MCFTG's.
Michael Wehar
CC BY-SA 4.0
2018-07-03T09:21:05.950Z
@MichaelWehar this already has been examined: http://www.aclweb.org/anthology/C04-1012
Andrey Lebedev
CC BY-SA 4.0
2018-07-03T14:09:23.007Z
Thank you very much for sharing this reference!!  So based on their result, possibly we could prove that your CFTG is not equivalent any MCFTG by showing that the string language associated with your CFTG cannot be generated by any TAG?
Michael Wehar
CC BY-SA 4.0
2018-07-03T14:12:32.010Z
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
<tree><grammars><context-free>
Example of context-free tree language which can not be generated by monadic CFTG
Andrey Lebedev
# Example of context-free tree language which can not be generated by monadic CFTG

(Asked by: username_0 on 2018-06-24)

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.

**Tags:** tree, grammars, context-free
> **Comments:**
> **username_0**: 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.  
> **username_1**: Consider the following CFTG.  Symbols: S has arity 0, T has arity 2, a has arity 0, and b has arity 2.  Grammar Rules: S() -> T(a, a), T(x, y) -> T(b(x, y), b(x, y)), T(x, y) -> b(x, y)  
> **username_1**: I don't have a proof that it does not have an equivalent MCFTG.  I just suspect that it might not have an equivalent MCFTG.  Please correct me if I'm wrong.  :)  
> **username_0**: 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$  
> **username_0**: 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!  
> **username_1**: Wow!!  Yes, you're right, there is an equivalent MCFTG to my grammar.  Let me think about yours.  :)  
> **username_1**: I thought about your grammar trying to see if I could find an equivalent MCFGT, but I wasn't able to come up with one.  This almost looks like an equivalent grammar: $S \rightarrow a(T_1, T_2)$, $T_1 \rightarrow b(T_1, T_2)$, $T_2 \rightarrow c(T_1, T_2)$, $T_1 \rightarrow a$, $T_2 \rightarrow a$  
> **username_1**: The reason that this does not work is because this grammar could generate a tree that is not balanced while your grammar only generates balanced trees.  
> **username_0**: That's exactly an idea to generated balanced trees with different labels in the left and right sides. Such a grammar seems to be not having an equivalent MCFTG!  
> **username_1**: I haven't yet come up with a proof for why your grammar has no equivalent MCFTG.  If it does not have an equivalent MCFTG, then I suspect we would be able to prove something much more general about the restrictiveness of MCFTG's.  
> **username_0**: @MichaelWehar this already has been examined: http://www.aclweb.org/anthology/C04-1012  
> **username_1**: Thank you very much for sharing this reference!!  So based on their result, possibly we could prove that your CFTG is not equivalent any MCFTG by showing that the string language associated with your CFTG cannot be generated by any TAG?  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_0 on 2018-07-03. Score: 1 | Accepted answer

Based on the comment of [Michael Wehar](https://cstheory.stackexchange.com/users/14207/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.

> **Comments:**
> **username_1**: 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.  :)  

---

