L系統

Lindenmayer系統，簡稱L系統，是由荷兰烏特勒支大學的生物学和植物学家，匈牙利裔的阿里斯蒂德·林登麦伊尔（Aristid Lindenmayer）於1968年提出的有关生长发展中的细胞交互作用的数学模型，尤其被廣泛應用於植物生長過程的研究。

使用 L-系統 生成的 3D 雜草

L-system是一系列不同形式的正规语法规则，多被用于植物生长过程建模，但是也被用于模拟各种生物体的形态。L-system也能用于生成自相似的分形，例如迭代函数系统。

起源

作为一位生物学家，Lindenmayer工作的内容是酵母菌和丝状真菌，并研究多种类型的海藻的生长模式，例如蓝绿细菌项圈藻（Anabaena catenula，淡水藻类的一种）。最初，L系统被设计成用于提供一种关于简单多细胞生物体生长的正规描述，并且试图证明植物细胞之间的紧密关系。不久以后，这个系统被扩展成描述高等植物及其复杂枝杈结构。

L-system 结构

L-system的自然递归规则导致自相似性，也因此使得分形一类形式可以很容易的使用L-system描述。植物模型和自然界的有机结构生成，非常相似并很容易被定义，因此通过增加递归的层数，可以缓慢生长并逐渐变得更复杂。L-system同样在制造人造生命领域。 L-system 语法与Chomsky语法非常相似，說到L-system通常指的是带参数的L-system，定义如下：

G＝｛V,S,ω,P},

V:变量符号集合

S：常量符号集合

ω：初始状态串

P：产生式规则

自初始狀態開始迭代套入L-system的文法規則，和正規文法所產生的語言不同處在於，L-system在一次迭代中可同時套用許多不同的文法規則。如果在一次迭代中只能夠套用一個文法規則，產生出來的結果被稱為語言而不是L-system。由此可知，L-system為正規文法所產生出的語言的子集合。

L系统的例子

例1：海藻的生长

Lindenmayer研究海藻生长模式时提出的最早的L-系统：

变量 : A B

常量 : 无

公理  : A

规则  : (A → AB), (B → A)

迭代过程：

n = 0 : A

n = 1 : AB

n = 2 : ABA

n = 3 : ABAAB

n = 4 : ABAABABA

n = 5 : ABAABABAABAAB

n = 6 : ABAABABAABAABABAABABA

n = 7 : ABAABABAABAABABAABABAABAABABAABAAB

例1的解释

n=0: A 开始 (公理/起始点) / \ n=1: A B 根据规则(A → AB)起始点A拓展成AB，由于起始点没有B，规则(B → A)没有被用到 /| \ n=2: A B A AB中的A拓展成AB，B变成A，于是得到了ABA /| | |\ n=3: A B A A B 可以看到每个A都是一个新的子树的根，由此引发出和整体结构同构的子结构。 /| | |\ |\ \ n=4: A B A A B A B A 

如果我们观察这个序列的长度就会发现这是一个斐波那契数列—— 1 2 3 5 8 13 21 34 55 89 ... （因为我们选择从A开始，故第一个1少掉了） 如果我们把A看成一只成年兔子，B看成未成年兔子，那么这个构造和那个著名的兔生兔的构造是一致的。 即每个月B会成长成A，而A每个月又会生出一个B。

开放问题

许多涉及L-systems研究的问题有待解决，比如：

• 描述所有那些确定的局部连锁的上下文无关L-systems（目前已知完成解决的只有包含两个变量的这一种情况）。
• 给定一个结构，找出生成此结构的L-systems文法。

参考文献

外部連結

维基共享资源中相关的多媒体资源：L系統

• Algorithmic Botany at the University of Calgary （页面存档备份，存于互联网档案馆）
• Branching: L-system Tree （页面存档备份，存于互联网档案馆）　A Java applet of the botanical tree growth simulation using the L-system.
• 。Brief description of L-systems and how the strings they generate can be interpreted by computer.
• "powerPlant" an open-source landscape modelling software （页面存档备份，存于互联网档案馆）
• L-Systems in Architecture （页面存档备份，存于互联网档案馆）
• An evolutionary L-systems generator (anyos*) （页面存档备份，存于互联网档案馆）
• . Page at Pawfal ("poor artists working for a living") about using L-systems and genetic algorithms to generate music.
• eXtended L-Systems (XL), Relational Growth Grammars, and open-source software platform GroIMP. （页面存档备份，存于互联网档案馆）
• A JAVA applet with many fractal figures generated by L-systems. （页面存档备份，存于互联网档案馆）
• L-systems in Plant Growth,Simulation and Visualization (PlantVR). （页面存档备份，存于互联网档案馆）
• Musical L-systems: Theory and applications about using L-systems to generate musical structures, from waveforms to macro-forms. （页面存档备份，存于互联网档案馆）
• - Interactive L-System interpreter using the Canvas HTML element。
• 。
• Fractal Grower: Free Java paper folding L-System intended for elementary and middle school students. （页面存档备份，存于互联网档案馆）
• Programmatic animations in actionscript showing various L-systems. （页面存档备份，存于互联网档案馆）
• Java applet showing random L-Systems while driving down Lindenmayer Boulevard （页面存档备份，存于互联网档案馆）
• Magic Garden - Artificial Plants Laboratory （页面存档备份，存于互联网档案馆） - free plants generator using L-Systems
• Inkscape （页面存档备份，存于互联网档案馆） a free software vector graphics program which implements, among its plugins, an L-system generator
• ，an interactive evolutionary image generator based in L-Systems
• Online experiments with L-Systems using JSXGraph (JavaScript) （页面存档备份，存于互联网档案馆）

参见

•  数学主题
•  植物主题

• 分形
• 迭代函數系統
• 希爾伯特曲線
• 图灵机
• 图灵归约
• 交互式证明系统
• 隨機預言機