Encoding of binary trees as a regular language? There are many ways of representing binary trees as strings.  For example, I could encode a tree as either nil or a pair of trees, such as

(nil, ((nil, nil), nil))


This representation has a simple CFG:

S -&gt; nil
S -&gt; (S, S)


My question is whether there exists some representation of binary trees as a string such that the set of all binary tree encodings is a regular language.  I have a suspicion that this cannot be done due to some pumping-lemma-based argument, but I have no idea how to go about showing this.

Does such a representation exist?
As Peter Shor mentions in a comment, the number of full binary trees with $n+1$ leaves is given by the $n$-th Catalan number $C_n$. It is known that the Catalan numbers have generating function

$C(x) = \frac{1-\sqrt{1-4x}}{2x}$.

On the other hand, it is known (Chomsky, Schützenberger; 1963) that regular languages have rational generating functions.

Clearly, $C$ is not rational. This implies that there is no regular encoding of full binary trees where each tree has a unique representation.

(Note that the generating function of arbitrary binary trees is not rational, either.)