The topology of language

Based on ideas from information theory, in particular the method of arithmetic coding, we describe a metric on sets of strings. In fact, these spaces correspond exactly with compact ultrametric spaces, and we explore their properties in detail. In particular, we look at contraction mappings in these spaces, as they are of fundamental importance in building fractals. We introduce a connection between fractal geometry and formal language theory. There are a number of parallels that can be drawn between the operations that are carried out on fractals and those that occur in formal language theory, and this leads to speculation about how deep the connection goes.