Some sets of ordered binary trees can be represented as a CFG with rules of the form
A -> aBC
A -> b
Where A,B,C
are nonterminals and a
and b
are terminals representing internal nodes and leaf nodes respectively. The tree can be recovered from any word in the language by a preorder traversal.
The set of all such grammars forms a class of languages which is a subset of context free languages but isomorphic to a superset of regular languages (by unary encoding the alphabet and adding a dummy terminal for the second nonterminal in every production). It is obviously closed under union as you can simply concatenate the lists of productions to get a new tree grammar.
My question is whether this class is closed under intersection. I have been unable to prove that is either closed or not closed, and I figured I should see if anyone else can see how to do this.