The complexity exhibited by cellular automata is studied using both to
pological (graph-theoretical) and metric (thermodynamic) techniques. A
novel topological classification, based on a hierarchy of languages,
is introduced. In particular, it is shown that the elementary rule 22
is able to produce, upon iteration, a deep nesting of grammatical rule
s and that this asymptotically yields a phase transition when the ther
modynamic formalism is applied to the limit spatial configuration.