An L-system or Lindenmayer system is a parallel rewriting system, namely a variant of a formal grammar, most famously used to model the growth processes of plant development, but also able to model the morphology of a variety of organisms. L-systems can also be used to generate self-similar fractals such as iterated function systems. L-systems were introduced and developed in 1968 by the Hungarian theoretical biologist and botanist from the University of Utrecht, Aristid Lindenmayer (1925–1989).
Saturday, 12 March 2011
Origins
As a biologist, Lindenmayer worked with yeast and filamentous fungi and studied the growth patterns of various types of algae, such as the blue/green bacteria Anabaena catenula. Originally the L-systems were devised to provide a formal description of the development of such simple multicellular organisms, and to illustrate the neighbourhood relationships between plant cells. Later on, this system was extended to describe higher plants and complex branching structures.
L-system structure
The recursive nature of the L-system rules leads to self-similarity and thereby fractal-like forms which are easy to describe with an L-system. Plant models and natural-looking organic forms are similarly easy to define, as by increasing the recursion level the form slowly 'grows' and becomes more complex. Lindenmayer systems are also popular in the generation of artificial life.
L-system grammars are very similar to the semi-Thue grammar (see Chomsky hierarchy). L-systems are now commonly known as parametric L systems, defined as a tuple
G = (V, ω, P),
where
* V (the alphabet) is a set of symbols containing elements that can be replaced (variables)
* ω (start, axiom or initiator) is a string of symbols from V defining the initial state of the system
* P is a set of production rules or productions defining the way variables can be replaced with combinations of constants and other variables. A production consists of two strings, the predecessor and the successor. For any symbol A in V which does not appear on the left hand side of a production in P, the identity production A → A is assumed; these symbols are called constants.
The rules of the L-system grammar are applied iteratively starting from the initial state. As many rules as possible are applied simultaneously, per iteration; this is the distinguishing feature between an L-system and the formal language generated by a formal grammar. If the production rules were to be applied only one at a time, one would quite simply generate a language, rather than an L-system. Thus, L-systems are strict subsets of languages.
An L-system is context-free if each production rule refers only to an individual symbol and not to its neighbours. Context-free L-systems are thus specified by either a prefix grammar, or a regular grammar. If a rule depends not only on a single symbol but also on its neighbours, it is termed a context-sensitive L-system.
If there is exactly one production for each symbol, then the L-system is said to be deterministic (a deterministic context-free L-system is popularly called a D0L-system). If there are several, and each is chosen with a certain probability during each iteration, then it is a stochastic L-system.
Using L-systems for generating graphical images requires that the symbols in the model refer to elements of a drawing on the computer screen. For example, the program Fractint uses turtle graphics (similar to those in the Logo programming language) to produce screen images. It interprets each constant in an L-system model as a turtle command.
L-system grammars are very similar to the semi-Thue grammar (see Chomsky hierarchy). L-systems are now commonly known as parametric L systems, defined as a tuple
G = (V, ω, P),
where
* V (the alphabet) is a set of symbols containing elements that can be replaced (variables)
* ω (start, axiom or initiator) is a string of symbols from V defining the initial state of the system
* P is a set of production rules or productions defining the way variables can be replaced with combinations of constants and other variables. A production consists of two strings, the predecessor and the successor. For any symbol A in V which does not appear on the left hand side of a production in P, the identity production A → A is assumed; these symbols are called constants.
The rules of the L-system grammar are applied iteratively starting from the initial state. As many rules as possible are applied simultaneously, per iteration; this is the distinguishing feature between an L-system and the formal language generated by a formal grammar. If the production rules were to be applied only one at a time, one would quite simply generate a language, rather than an L-system. Thus, L-systems are strict subsets of languages.
An L-system is context-free if each production rule refers only to an individual symbol and not to its neighbours. Context-free L-systems are thus specified by either a prefix grammar, or a regular grammar. If a rule depends not only on a single symbol but also on its neighbours, it is termed a context-sensitive L-system.
If there is exactly one production for each symbol, then the L-system is said to be deterministic (a deterministic context-free L-system is popularly called a D0L-system). If there are several, and each is chosen with a certain probability during each iteration, then it is a stochastic L-system.
Using L-systems for generating graphical images requires that the symbols in the model refer to elements of a drawing on the computer screen. For example, the program Fractint uses turtle graphics (similar to those in the Logo programming language) to produce screen images. It interprets each constant in an L-system model as a turtle command.
Examples of L-systems
Example 1: Algae
Lindenmayer's original L-system for modelling the growth of algae.
variables : A B
constants : none
start : A
rules : (A → AB), (B → A)
which produces:
n = 0 : A
n = 1 : AB
n = 2 : ABA
n = 3 : ABAAB
n = 4 : ABAABABA
n = 5 : ABAABABAABAAB
n = 6 : ABAABABAABAABABAABABA
n = 7 : ABAABABAABAABABAABABAABAABABAABAAB
Example 1: Algae, explained
n=0: A start (axiom/initiator)
/ \
n=1: A B the initial single A spawned into AB by rule (A → AB), rule (B → A) couldn't be applied
/| \
n=2: A B A former string AB with all rules applied, A spawned into AB again, former B turned into A
/| | |\
n=3: A B A A B note all A's producing a copy of themselves in the first place, then a B, which turns ...
/| | |\ |\ \
n=4: A B A A B A B A ... into an A one generation later, starting to spawn/repeat/recurse then
Example 2: Fibonacci numbers
If we define the following simple grammar:
variables : A B
constants : none
start : A
rules : (A → B), (B → AB)
then this L-system produces the following sequence of strings:
n = 0 : A
n = 1 : B
n = 2 : AB
n = 3 : BAB
n = 4 : ABBAB
n = 5 : BABABBAB
n = 6 : ABBABBABABBAB
n = 7 : BABABBABABBABBABABBAB
These are the mirror images of the strings from the first example, with A and B interchanged. Once again, each string is the concatenation of the preceding two, but in the reversed order.
In either example, if we count the length of each string, we obtain the famous Fibonacci sequence of numbers:
1 1 2 3 5 8 13 21 34 55 89 ...
For n>0, if we count the kth position from the invariant end of the string (left in Example 1 or right in Example 2), the value is determined by whether a multiple of the golden mean falls within the interval (k-1,k). The ratio of A to B likewise converges to the golden mean.
This example yields the same result (in terms of the length of each string, not the sequence of As and Bs) if the rule (B → AB) is replaced with (B → BA).
This sequence is a locally catenative sequence because G(n) = G(n-2)G(n-1) where G(n) is the nth generation.
Example 3: Cantor dust
Cantor set in seven iterations.svg
variables : A B
constants : none
start : A {starting character string}
rules : (A → ABA), (B → BBB)
Let A mean "draw forward" and B mean "move forward".
This produces the famous Cantor's fractal set on a real straight line R.
Example 4: Koch curve
A variant of the Koch curve which uses only right-angles.
variables : F
constants : + −
start : F
rules : (F → F+F−F−F+F)
Here, F means "draw forward", + means "turn left 90°", and - means "turn right 90°" (see turtle graphics).
n = 0: Koch Square - 0 iterations
F
n = 1: Koch Square - 1 iterations
F+F-F-F+F
n = 2: Koch Square - 2 iterations
F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F
n = 3: Koch Square - 3 iterations
F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+ F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F- F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F- F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+ F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F
Example 5: Penrose tilings
The following images were generated by an L-system. They are related and very similar to Penrose tilings, invented by Roger Penrose.
Penam01c.gif
Penam02c.gif
As an L-system these tilings are called Penrose's rhombuses and Penrose's tiles. The above pictures were generated for n = 6 as an L-system. If we properly superimpose Penrose tiles as an L-system we get next tiling:
Pend05c.gif
otherwise we get patterns which do not cover an infinite surface completely:
Pendx05c.gif
Example 6: Sierpinski triangle
The Sierpinski triangle drawn using an L-system.
variables : A B
constants : + −
start : A
rules : (A → B−A−B), (B → A+B+A)
angle : 60°
Here, A and B both mean "draw forward", + means "turn left by angle", and − means "turn right by angle" (see turtle graphics). The angle changes sign at each iteration so that the base of the triangular shapes are always in the bottom (they would be in the top and bottom, alternatively, otherwise).
Serpinski Lsystem.svg
Evolution for n = 2, n = 4, n = 6, n = 8
There is another way to draw the Sierpinski triangle using an L-system.
variables : F G
constants : + −
start : F−G−G
rules : (F → F−G+F+G−F), (G → GG)
angle : 120°
Here, F and G both mean "draw forward", + means "turn left by angle", and − means "turn right by angle".
Example 7: Dragon curve
The dragon curve drawn using an L-system.
variables : X Y
constants : F + −
start : FX
rules : (X → X+YF), (Y → FX-Y)
angle : 90°
Here, F means "draw forward", - means "turn left 90°", and + means "turn right 90°". X and Y do not correspond to any drawing action and are only used to control the evolution of the curve.
Dragon curve L-system.svg
Dragon curve for n = 10
Example 8: Fractal plant
variables : X F
constants : + −
start : X
rules : (X → F-[[X]+X]+F[+FX]-X), (F → FF)
angle : 25°
Here, F means "draw forward", - means "turn left 25°", and + means "turn right 25°". X does not correspond to any drawing action and is used to control the evolution of the curve. [ corresponds to saving the current values for position and angle, which are restored when the corresponding ] is executed.
Fractal-plant.svg
Fractal plant for n = 6
Example 9: Modified Koch L-system
A fractal figure drawn introducing a periodic change of angle sign in the iteration of the usual Koch curve L-system.
Lindenmayer's original L-system for modelling the growth of algae.
variables : A B
constants : none
start : A
rules : (A → AB), (B → A)
which produces:
n = 0 : A
n = 1 : AB
n = 2 : ABA
n = 3 : ABAAB
n = 4 : ABAABABA
n = 5 : ABAABABAABAAB
n = 6 : ABAABABAABAABABAABABA
n = 7 : ABAABABAABAABABAABABAABAABABAABAAB
Example 1: Algae, explained
n=0: A start (axiom/initiator)
/ \
n=1: A B the initial single A spawned into AB by rule (A → AB), rule (B → A) couldn't be applied
/| \
n=2: A B A former string AB with all rules applied, A spawned into AB again, former B turned into A
/| | |\
n=3: A B A A B note all A's producing a copy of themselves in the first place, then a B, which turns ...
/| | |\ |\ \
n=4: A B A A B A B A ... into an A one generation later, starting to spawn/repeat/recurse then
Example 2: Fibonacci numbers
If we define the following simple grammar:
variables : A B
constants : none
start : A
rules : (A → B), (B → AB)
then this L-system produces the following sequence of strings:
n = 0 : A
n = 1 : B
n = 2 : AB
n = 3 : BAB
n = 4 : ABBAB
n = 5 : BABABBAB
n = 6 : ABBABBABABBAB
n = 7 : BABABBABABBABBABABBAB
These are the mirror images of the strings from the first example, with A and B interchanged. Once again, each string is the concatenation of the preceding two, but in the reversed order.
In either example, if we count the length of each string, we obtain the famous Fibonacci sequence of numbers:
1 1 2 3 5 8 13 21 34 55 89 ...
For n>0, if we count the kth position from the invariant end of the string (left in Example 1 or right in Example 2), the value is determined by whether a multiple of the golden mean falls within the interval (k-1,k). The ratio of A to B likewise converges to the golden mean.
This example yields the same result (in terms of the length of each string, not the sequence of As and Bs) if the rule (B → AB) is replaced with (B → BA).
This sequence is a locally catenative sequence because G(n) = G(n-2)G(n-1) where G(n) is the nth generation.
Example 3: Cantor dust
Cantor set in seven iterations.svg
variables : A B
constants : none
start : A {starting character string}
rules : (A → ABA), (B → BBB)
Let A mean "draw forward" and B mean "move forward".
This produces the famous Cantor's fractal set on a real straight line R.
Example 4: Koch curve
A variant of the Koch curve which uses only right-angles.
variables : F
constants : + −
start : F
rules : (F → F+F−F−F+F)
Here, F means "draw forward", + means "turn left 90°", and - means "turn right 90°" (see turtle graphics).
n = 0: Koch Square - 0 iterations
F
n = 1: Koch Square - 1 iterations
F+F-F-F+F
n = 2: Koch Square - 2 iterations
F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F
n = 3: Koch Square - 3 iterations
F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+ F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F- F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F- F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+ F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F
Example 5: Penrose tilings
The following images were generated by an L-system. They are related and very similar to Penrose tilings, invented by Roger Penrose.
Penam01c.gif
Penam02c.gif
As an L-system these tilings are called Penrose's rhombuses and Penrose's tiles. The above pictures were generated for n = 6 as an L-system. If we properly superimpose Penrose tiles as an L-system we get next tiling:
Pend05c.gif
otherwise we get patterns which do not cover an infinite surface completely:
Pendx05c.gif
Example 6: Sierpinski triangle
The Sierpinski triangle drawn using an L-system.
variables : A B
constants : + −
start : A
rules : (A → B−A−B), (B → A+B+A)
angle : 60°
Here, A and B both mean "draw forward", + means "turn left by angle", and − means "turn right by angle" (see turtle graphics). The angle changes sign at each iteration so that the base of the triangular shapes are always in the bottom (they would be in the top and bottom, alternatively, otherwise).
Serpinski Lsystem.svg
Evolution for n = 2, n = 4, n = 6, n = 8
There is another way to draw the Sierpinski triangle using an L-system.
variables : F G
constants : + −
start : F−G−G
rules : (F → F−G+F+G−F), (G → GG)
angle : 120°
Here, F and G both mean "draw forward", + means "turn left by angle", and − means "turn right by angle".
Example 7: Dragon curve
The dragon curve drawn using an L-system.
variables : X Y
constants : F + −
start : FX
rules : (X → X+YF), (Y → FX-Y)
angle : 90°
Here, F means "draw forward", - means "turn left 90°", and + means "turn right 90°". X and Y do not correspond to any drawing action and are only used to control the evolution of the curve.
Dragon curve L-system.svg
Dragon curve for n = 10
Example 8: Fractal plant
variables : X F
constants : + −
start : X
rules : (X → F-[[X]+X]+F[+FX]-X), (F → FF)
angle : 25°
Here, F means "draw forward", - means "turn left 25°", and + means "turn right 25°". X does not correspond to any drawing action and is used to control the evolution of the curve. [ corresponds to saving the current values for position and angle, which are restored when the corresponding ] is executed.
Fractal-plant.svg
Fractal plant for n = 6
Example 9: Modified Koch L-system
A fractal figure drawn introducing a periodic change of angle sign in the iteration of the usual Koch curve L-system.
Open problems
There are many open problems involving studies of L-systems. For example:
* Characterisation of all the deterministic context-free L-systems which are locally catenative. (A complete solution is known only in the case where there are only two variables).
* Given a structure, find an L-system that can produce that structure.
* Characterisation of all the deterministic context-free L-systems which are locally catenative. (A complete solution is known only in the case where there are only two variables).
* Given a structure, find an L-system that can produce that structure.
Types of L-systems
L-systems on the real line R:
* Prouhet-Thue-Morse system
Well-known L-systems on a plane R2 are:
* space-filling curves (Hilbert curve, Peano's curves, Dekking's church, kolams),
* median space-filling curves (Lévy C curve, Harter-Heighway dragon curve, Davis-Knuth terdragon),
* tilings (sphinx tiling, Penrose tiling),
* trees, plants, and the like.
* Prouhet-Thue-Morse system
Well-known L-systems on a plane R2 are:
* space-filling curves (Hilbert curve, Peano's curves, Dekking's church, kolams),
* median space-filling curves (Lévy C curve, Harter-Heighway dragon curve, Davis-Knuth terdragon),
* tilings (sphinx tiling, Penrose tiling),
* trees, plants, and the like.
Books
* Przemyslaw Prusinkiewicz, Aristid Lindenmayer - The Algorithmic Beauty of Plants PDF version available here for free
* Grzegorz Rozenberg, Arto Salomaa - Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology ISBN 978-3-540-55320-5
* Grzegorz Rozenberg, Arto Salomaa - Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology ISBN 978-3-540-55320-5
Subscribe to:
Posts (Atom)