Lsystem
Lsystem (L system, Lindenmayer system) is the algorithm that I describe the structure of various natural objects which assumed the growth process of the plant the beginning with a kind of the formal grammar and can express. When I generate prorepetition function (Iterated Function System; IFS) socalled selfresemblance figure and fractal figure of the natural object, I am used. LSystem made a theory biologist of the Utrecht University of Hungary in 1968, and I was proposed by Alice Ted Linden Mayer (Aristid Lindenmayer) who was a botanist and developed.
Table of contents
Origin
Linden Mayer studied the growth pattern of various creatures including the alga such as Anabaena catenula of yeast and a filamentous fungus and the bluegreen alga as a biologist. Originally Lsystem was developed to describe the mutual relations of the cell of the neighborhood in a growth style and the plant cell of such a unicellular organism or the simple multicellular organism of the system. Lsystem accomplishes development as a tool to describe the form of the higher plant and complicated divergence structure later.
Structure of Lsystem
The basics of Lsystem can easily describe the shape such as the selfresemblance figure and fractal figure in recurrence characteristics. A plant and other appearances can easily define the natural creature structure equally, and structure does "growth" by increasing the number of times of the recurrence summons and seems to become complicated. Lsystem is used for generation of the artificial life well.
(→ Chomsky hierarchy) where the grammar of Lsystem is similar to a thing of en:Unrestricted grammar. I am often defined now by four following groups.
 G = {V, S,ω, P},
Each element,
 V (letter): The set of the variable rearranged sequentially by a substituted rule (later P). When a recursive repetition calculation of Lsystem advances, it is character string consisting of elements of this V that make "growth" as a thing.
 S ： A set of the fixed number not to change even if a calculation advances.
 ω ： The character string consisting of elements of V indicating the initial state of the system.
 P ： The set of the substituted rule changing V. Each element is described, for example, like (A → AB) by a combination of (substituted object) character string and character string after the substitution before substitution.
When a substituted object is only an independent letter in substituted rule P, Lsystem is contextfree language. On the other hand, Lsystem is a contextsensitive language when a substituted rule considers it to the mutual relations with the letter of the neighborhood. In addition, it is said, "it is deterministic", and Lsystem is called D0Lsystem (deterministic contextfree Lsystem) when substituted rule P is applied for each letter surely every time. On the contrary, "it is probabilistic" and is called Lsystem when the application of the substituted rule depends on the probability.
When you apply Lsystem to graphics, you must convert the character string that Lsystem generates into the figure on the screen in one way or another. For example, by the program (cf. outside link of the end of a sentence) called FractInt, I generate graphics using a turtle such as LOGO. In other words, a program translates character string of Lsystem into the control order of the turtle and lets a figure paint pictures.
Example of Lsystems
It is alga example 1
The example which describes the algal growth that was an opportunity of the Lsystem birth.
 V ： A, B
 S ： Unavailable
 ω: A
 P ： (A → AB) (B → A)
The character string grows up as follows when I calculate sequentially.
 n = 0 ： A
 n = 1 ： AB
 n = 2 ： ABA
 n = 3 ： ABAAB
 n = 4 ： ABAABABA
In this example, (A → AB) expresses what normal cell A and unripe cell B produce by unequal cell division in substituted rule P and expresses that (B → A) matures to cell A which unripe cell B grows up, and can be divided. Because a figure does this character string (e.g., I replace B with the figures of the small cell a cell of the branching type each in A), I can get the picture such as the algal colony which unfolded on the agar nutrient medium.
It is Fibonacci series example 2
 V ： A, B
 S ： Unavailable
 ω: A
 P ： (A → B) (B → AB)
It becomes the following character string when I push forward a calculation.
 n = 0 ： A
 n = 1 ： B
 n = 2 ： AB
 n = 3 ： BAB
 n = 4 ： ABBAB
 n = 5 ： BABABBAB
 n = 6 ： ABBABBABABBAB
 n = 7 ： BABABBABABBABBABABBAB
When count the number of each letter of this character string sequentially from n=0; Fibonacci series (1 1 2 3 5 8 13 21 34 55 89 …It becomes). Because the contents of the character string do not matter, and they pay attention only to length in this example, I can get similar progression even if, for example, I rearrange (B → AB) of the substitution rule in (B → BA).
It is Cantor meeting example 3
 V ： A, B
 S ： Unavailable
 ω: A
 P ： (A → ABA) (B → BBB)
It becomes the following character string when I push forward a calculation.
 n = 0 ： A
 n = 1 ： ABA
 n = 2 ： ABABBBABA
 n = 3 ： ABABBBABABBBBBBBBBABABBBABA
The figure such as the bottom is provided when I replace A of this character string with the part that B was pulled out for a line. I am equivalent to operation that (A → ABA) of the substituted rule divides (closed interval) for a line into 3 parts and pulls out the center. (B → BBB) means that a removed section does not return once. Specifically, Cantor set (Cantor set) is referred to
It is Koch curve example 4
A drawing example of the Koch curve to be comprised of a right angle.
 V ： F
 S ： +, ,
 ω: F
 P ： (F → F+FFF+F)
In the above, in F, in drawing, + of the straight line by the turtle,  means that 90 degrees turns to the right a 90 degrees turn in a turtle in the same way to the left. The following figures are provided when I calculate this sequentially.
F
F+FFF+F
F+FFF+F+F+FFF+FF+FFF+FF+FFF+F+F+FFF+F
F+FFF+F+F+FFF+FF+FFF+FF+FFF+F+F+FFF+F+ F+FFF+F+F+FFF+FF+FFF+FF+FFF+F+F+FFF+F F+FFF+F+F+FFF+FF+FFF+FF+FFF+F+F+FFF+F F+FFF+F+F+FFF+FF+FFF+FF+FFF+F+F+FFF+F+ F+FFF+F+F+FFF+FF+FFF+FF+FFF+F+F+FFF+F
It is Penrose tile example 5
Using Lsystem, I can generate the plane filling design such as the chart below. Specifically, I refer to Penrose tile and Roger Penrose.
It is the triangle of the shell pin ski example 6
The example which draws a figure of the triangle of the shell pin ski in Lsystem.
 V ： A, B
 S ： +, 
 ω: A
 P ： (A → BAB) (B → A+B+A)
In the above, in A and B, in drawing, + of the straight line by the turtle,  means that 60 degrees turns to the right a 60 degrees turn in a turtle in the same way to the left. There are other substituted rules representing similar figure, but, in the case of this rule, will begin to draw the turtle from the triangular lower left.
The figure which is drawn at the time of n = 2, n = 4, n = 6, n = 8 each. At the time of n →∞, I equal in the triangle of the shell pin ski.
It is transformation of the Koch curve example 7
Kind of the fractal figure which painted pictures while making the change of the periodic angle to normal Koch curve.
Graphics using other Lsystem
 Lichen or bryophytes:
 A herbaceous drawing figures example:
 A drawing figures example of Kimoto:
 Including the protozoan:

Known problem
A lot of problems about Lsystem exist, but it is difficult for the prime example to follow Lsystem adversely. Specifically, it is difficult parameter to generate the structure and to find a substituted rule when a certain structure was shown. This is remarkable in a figure formed after the process when it is complicated (the repetition number of times there is many) such as the natural object.
Kind of Lsystem
Lsystem in the true progression:
Lsystem in the plane:
 Plane filling curve, figure (Spacefilling curve) others:
Lsystem in the space:
 Natural object
Probabilistic Lsystem
Probabilistic (Stochastic) Lsystem expanded Lsystem and allowed you to diverge stochastically. Because probabilistic Lsystem does not have a standard, grammar varies according to software.
It is an example every implementation of probabilistic diverging Lsystem as follows.
Implementation of Tong Lin (1996)  Houdini (Lsystem SOP)  Cinema 4D (Turtle of MoSpline) 

A=(0.5)FA A=(0.25)+FA A=(0.25) F+A  A=FA: 0.5 A=+FA: 0.25 A=F+A: 0.25  A: (rnd(1)<0.5)=FA A: (rnd(1)<0.75)=+FA A: (rnd(1)>0.75)=F+A 
Contextdependent Lsystem
Contextdependent (Contextsensitive) Lsystem expanded Lsystem, and pattern matching allows divergence depending on context. For the thing which implemented contextdependent Lsystem, implementation of Tong Lin exists.
Allied item
References
 Przemyslaw Prusinkiewicz  en:The Algorithmic Beauty of Plants PDF version available here for free
Outside link
 David J. Wright's article on Lsystems
 Algorithmic Botany at the University of Calgary
 Branching: Java applet (English) which simulates the growth of the tree using Lsystem Tree Lsystem
 Fractint LSystem True Fractals
 "An introduction to Lindenmayer systems", by Gabriela Ochoa. Brief description of Lsystems and how the strings they generate can be interpreted by computer.
 "powerPlant" an opensource landscape modelling software
 Fractint home page
 "Lsystem in Falk arts" The FORMA commurative issue of the conference ISKFA06
 A simple Lsystems generator (Windows)
 Lyndyhop: another simple Lsystems generator (Windows & Mac)
 An evolutionary Lsystems generator (anyos*)
 Lsystems gallery – a tribute to Fractint
 "LsystemComposition". Page at Pawfal ("poor artists working for a living") about using Lsystems and genetic algorithms to generate music.
 eXtended LSystems (XL), Relational Growth Grammars, and opensource software platform GroIMP.
 A JAVA applet with many fractal figures generated by Lsystems.
 Lsystems in Architecture; genetic housing.
 Lsystems in Plant Growth,Simulation and Visualization (PlantVR).
 Musical Lsystems: Theory and applications about using Lsystems to generate musical structures, from waveforms to macroforms.
 LSys/JS  Interactive LSystem interpreter using the Canvas HTML element.
This article is taken from the Japanese Wikipedia Lsystem
This article is distributed by ccbysa or GFDL license in accordance with the provisions of Wikipedia.
In addition, Tranpedia is simply not responsible for any show is only by translating the writings of foreign licenses that are compatible with CCBYSA license information.
0 개의 댓글:
댓글 쓰기