History and Origins
History and Origins
Lindenmayer Systems
Lindenmayer Systems
A Lindenmayer system, or L-system, is a parallel rewriting system and a type of formal grammar.
June 23, 2017—Alessio Sarti
L-systems were introduced and developed in 1968 by Aristid Lindenmayer to capture the behavior of cell divisions in multicellular organisms, where many divisions may occur at the same time. Lindenmayer used them to model the growth patterns of algae and plants, but they can also be used for modeling fractals.
Derivation
Derivation
An L-system is defined by an alphabet of symbols that can be used to make strings, a collection of production rules that expand each symbol into some larger string of symbols, an initial “axiom” string from which to begin construction and a mechanism for translating the generated strings into geometric structures.
The first step is to create the alphabet:
In[1]:=
alphabet={"A","B"}
Out[1]=
{A,B}
Then we define the substitution rules:
In[2]:=
rules={"A""AB","B""A"}
Out[2]=
{AAB,BA}
Define the initial axiom:
In[3]:=
axiom="A"
Out[3]=
A
The first generation of the system is, by definition, the axiom:
In[4]:=
LSystem[0,axiom_,rules_]:=axiom
The following generations can be computed recursively:
In[5]:=
LSystem[generation_Integer,axiom_,rules_]:=StringReplace[LSystem[generation-1,axiom,rules],rules]
Example for these rules:
In[6]:=
Manipulate[LSystem[n,axiom,rules],{n,0,8,1}]
Out[29]=
The result is a sequence of Fibonacci words.
If we take the length of each string, we obtain the Fibonacci sequence:
In[7]:=
Manipulate[StringLength[LSystem[n,axiom,rules]],{n,0,16,1}]
Out[30]=
The ratio B to A converges to the golden ratio:
In[8]:=
Manipulate[N[Ratios[Map[StringCount[LSystem[n,axiom,rules],#]&,alphabet]][[1]]],{n,1,16,1}]
Out[31]=
Applications
Applications
Space-Filling Curves
Space-Filling Curves
FURTHER EXPLORATIONS
Iterated Function System
Fractal
Cantor Set
Sierpiński Triangle
Dragon Curve
Hilbert Curve
AUTHORSHIP INFORMATION
Alessio Sarti
06/23/17