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 -> nil S -> (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?