Citizendia

An L-system or Lindenmayer system is a parallel rewriting system, namely a variant of a formal grammar (a set of rules and symbols), most famously used to model the growth processes of plant development, but also able to model the morphology of a variety of organisms. In Formal semantics, Computer science and Linguistics, a formal grammar (also called formation rules) is a precise description of a Formal Plants are living Organisms belonging to the kingdom Plantae. [1] L-systems can also be used to generate self-similar fractals such as iterated function systems. In Mathematics, iterated function systems or IFS s are a method of constructing Fractals the resulting constructions are always Self-similar. L-systems were introduced and developed in 1968 by the Hungarian theoretical biologist and botanist from the University of Utrecht, Aristid Lindenmayer (1925–1989). Year 1968 ( MCMLXVIII) was a Leap year starting on Monday (link will display full calendar of the Gregorian calendar. A biologist is a Scientist devoted to and producing results in Biology through the study of Organisms Typically biologists study organisms and their relationship Botany, plant science(s, phytology, or plant biology is a branch of Biology and is the scientific study of plant Life Utrecht University ( Universiteit Utrecht in Dutch) is a University in Utrecht, The Netherlands. Aristid Lindenmeyer ( November 17, 1925 – October 30, 1989) was an Hungarian Biologist. Year 1925 ( MCMXXV) was a Common year starting on Thursday (link will display the full calendar of the Gregorian calendar. Year 1989 ( MCMLXXXIX) was a Common year starting on Sunday (link displays 1989 Gregorian calendar)

Contents

Origins

'Weeds', generated using an L-system in 3D.
'Weeds', generated using an L-system in 3D.

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. Yeasts are a growth form of eukaryotic Microorganisms classified in the kingdom Fungi, with about 1500 Species currently described A fungus (ˈfʌŋgəs is a eukaryotic Organism that is a member of the kingdom Fungi (ˈfʌndʒaɪ For Anabaena AJuss, a plant genus of the Euphorbiaceae, see its synonym Romanoa. 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. Recursion, in Mathematics and Computer science, is a method of defining functions in which the function being defined is applied within its own definition In Mathematics, a self-similar object is exactly or approximately similar to a part of itself (i A fractal is generally "a rough or fragmented geometric shape that can be split into parts each of which is (at least approximately a reduced-size copy of the whole" 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. Artificial life (commonly Alife or alife) is a field of study and an associated art form which examine Systems related to Life, its processes

L-system grammars are very similar to the semi-Thue grammar (see Chomsky hierarchy). In Computer science and Mathematics a Semi-Thue system (also called a string rewriting system) is a type of Term rewriting system Within the field of Computer science, specifically in the area of Formal languages, the Chomsky hierarchy (occasionally referred to as Chomsky–Schützenberger L-systems are now commonly known as parametric L systems, defined as a tuple

G = {V, S, ω, P},

where

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 grammar. A formal language is a set of words, ie finite strings of letters, or symbols. Grammar is the field of Linguistics that covers the Rules governing the use of any given natural language. 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. In Computer science, a prefix grammar is a type of string rewriting system consisting of a set of string rewriting rules and similar to a Formal Strictly regular grammars In Computer science, a right regular grammar (also called right linear grammar) is a Formal grammar ( N,

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 (see external links below) uses turtle graphics (similar to those in the Logo programming language) to produce screen images. Turtle graphics is a term in Computer graphics for a method of programming Vector graphics using a relative cursor (the " Turtle " Logo is a Computer programming language used for Functional programming. 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 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. In Mathematics, the Fibonacci numbers are a Sequence of numbers named after Leonardo of Pisa, known as Fibonacci 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 . In Mathematics, the Fibonacci numbers are a Sequence of numbers named after Leonardo of Pisa, known as Fibonacci . .

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).

Example 3: Cantor dust

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". In Mathematics, the Cantor set, introduced by German Mathematician Georg Cantor in 1883 (but discovered in 1875 by Henry John Stephen Smith

This produces the famous Cantor's fractal set on a real straight line R. In Mathematics, the Cantor set, introduced by German Mathematician Georg Cantor in 1883 (but discovered in 1875 by Henry John Stephen Smith

Example 4: Koch curve

A variant of the Koch curve which uses only right-angles. The Koch snowflake (or Koch star) is a mathematical Curve and one of the earliest Fractal curves to have been described

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). Turtle graphics is a term in Computer graphics for a method of programming Vector graphics using a relative cursor (the " Turtle "

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. A Penrose tiling is a nonperiodic tiling generated by an aperiodic set of Prototiles named after Roger Penrose, who investigated these sets Sir Roger Penrose, PhD, OM, FRS (born 8 August 1931) is an English Mathematical physicist and Emeritus

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:

otherwise we get patterns which do not cover an infinite surface completely:

Example 6: Sierpinski triangle

The Sierpinski triangle drawn using an L-system. The Sierpiński triangle, also called the Sierpiński gasket or the Sierpiński Sieve, is a Fractal named after Wacław Sierpiński who described

variables : A B
constants : + −
start  : A
rules  : (A → B−A−B),(B → A+B+A)
angle  : 60°

Here, A and B mean both "draw forward", + means "turn left by angle", and − means "turn right by angle" (see turtle graphics). Turtle graphics is a term in Computer graphics for a method of programming Vector graphics using a relative cursor (the " Turtle " 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).

Evolution for n = 2, n = 4, n = 6, n = 9

There is another way to draw the Sierpinski triangle using an L-system. The Sierpiński triangle, also called the Sierpiński gasket or the Sierpiński Sieve, is a Fractal named after Wacław Sierpiński who described

variables : F G
constants : + −
start  : F−G−G
rules  : (F → F−G+F+G−F),(G → GG)
angle  : 120°

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. A dragon curve is the generic name for any member of a family of self similar Fractal curves which can be approximated by recursive methods such as

variables : X Y F
constants : + −
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 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 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. The Koch snowflake (or Koch star) is a mathematical Curve and one of the earliest Fractal curves to have been described

Open problems

There are many open problems involving studies of L-systems. For example:

Types of L-systems

L-systems on the real line R:

Well-known L-systems on a plane R2 are:

Books

Notes

  1. ^ Grzegorz Rozenberg and Arto Salomaa. The Algorithmic Beauty of Plants is a book by Przemyslaw Prusinkiewicz and Aristid Lindenmayer. The mathematical theory of L systems (Academic Press, New York, 1980). ISBN 0125971400

See also

External links

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic