Automata, Language and Iterated Function Systems

Przemyslaw Prusinkiewicz and Mark Hammel


The original method for approximating the attractor A of an iterated function system F = { F1 ,... , Fn } consists of selecting a starting point x0 and applying sequences of transformations from F to it. These sequences may be chosen at random or in a deterministic fashion, but regardless of the approach used, any sequence applied to x0 ∈ A yields a point y that also belongs to A. In contrast, the generalization of IFS's discussed in these notes introduces a control mechanism that restricts the set of applicable transformations to a (regular) language L over the alphabet F. Thus, in language-restricted iterated function systems (LRIFS's), only some sequences of transformations applied to x0 ∈ A yield points y in A. LRIFS's are more powerful than the ordinary IFS's, in the sense that some attractors of LRIFS's cannot be generated by IFS's. In addition, restrictions on transformation application make it possible to avoid non-invertible affine mappings which are incompatible with the escape-time method for visualizing the attractors. These notes describe the concept of LRIFS, illustrate it using examples, and relate it to other methods for generating fractals, such as the Koch construction and L-systems: The bibliography lists recent papers on the topic.


Przemyslaw Prusinkiewicz and Mark Hammel. Automata, Language and Iterated Function Systems. In Lecture notes for the SIGGRAPH '91 course: "Fractal Modeling in 3D Computer Graphics and Imagery".

Download PDF here (3.6 Mb).