Tag Archives: Formal Languages

Regular Encoding of Binary Trees

A couple of months ago, a question on cstheory.SE asked whether there is a regular encoding of binary trees. My immediate gut feeling was: no way! Binary trees are equivalent to Dyck words and the language of those is not regular1.

I was able to back this feeling with an approach using generating functions. I showed that the number of binary trees with $$n$$ nodes does not have a rational generating function; as all regular languages have rational structure functions, I claimed that this shows that binary trees can not be encoded with a regular language. This argument turned out to be somewhat fishy or incomplete since an encoding does not have to map all trees of size $$n$$ to encodings of size $$f(n)$$; at this point, the counting argument breaks down.

1. Easily shown with Pumping Lemma for regular languages.