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 regular¹.

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. Read more »