L系统

跳转至导航跳转至搜索L系统或Lindenmayer系统是并行重写系统，是形式语法的一种。 L系统由可用于制作字符串的符号字母，一系列将每个符号扩展为更大的符号字符串的生产规则，一个初始＆＃34;组成。公理开始构造的弦，以及将生成的弦转换为几何结构的机制。 L系统是由乌特勒支大学的匈牙利理论生物学家和植物学家Aristid Lindenmayer于1968年引入和开发的。 [1] Lindenmayer使用L系统描述植物细胞的行为并为植物发育的生长过程建模。 L系统也已用于模拟各种生物的形态[2]，并可用于生成自相似的分形。

作为生物学家，林登迈耶研究酵母和丝状真菌，研究了各种细菌的生长模式，例如蓝细菌鱼腥藻。最初，L系统被设计用来提供这种简单多细胞生物发展的正式描述，并说明植物细胞之间的邻域关系。后来，该系统扩展为描述更高的植物和复杂的分支结构。 [3]

L系统规则的递归性质导致自相似性，因此，很容易用L系统描述类似分形的形式。植物模型和看起来自然的有机形式很容易定义，因为通过逐渐增加递归级别，可以缓慢地“增长”该形式。并且变得更加复杂。 Lindenmayer系统在人工生命的产生中也很流行。

L系统语​​法与半Thue语法非常相似（请参阅Chomsky层次结构）。 L系统现在通常称为参数L系统，定义为元组

V（字母）是一组符号，其中既包含可替换的元素（变量），也包含不可替换的元素（＆＃34; constants＆＃34;或＆＃34; terminals＆＃34;）

ω（开始，公理或发起者）是来自V的符号字符串，定义系统的初始状态

P是一组生产规则或生产，定义了可以用常量和其他变量的组合替换变量的方式。一个产品由两个字符串组成，即前任和后继。对于没有出现在P的产品左侧的任何符号A，它是集合V的成员，则假定产品A→A。这些符号称为常数或终端。 （请参见《身份法》）。

L系统语​​法规则从初始状态开始迭代应用。每次迭代同时应用尽可能多的规则。每次迭代都使用尽可能多的规则这一事实将L系统与形式语法生成的形式语言区分开来，形式语法每次迭代仅应用一个规则。如果一次只应用一个生产规则，那么一个人会很简单地生成一种语言，而不是一种L系统。 [需要澄清]因此，L系统是语言的严格子集。 [需要澄清]

如果每个生产规则仅引用单个符号而不引用其邻居，则L系统不受上下文限制。因此，无上下文的L系统由无上下文的语法指定。如果一个规则不仅取决于单个符号，还取决于其相邻元素，则将其称为上下文相关的L系统。

如果每个符号正好有一个乘积，则称L系统是确定性的（确定性上下文无关L系统通常称为D0L系统）。如果有多个，并且在每次迭代期间都以一定的概率选择了每个，则它是一个随机L系统。

使用L系统生成图形图像需要模型中的符号引用计算机屏幕上图形的元素。例如，程序Fractint使用乌龟图形（类似于Logo编程语言中的图形）来产生屏幕图像。它将L系统模型中的每个常量解释为turtle命令。

n = 0：起始（公理/发起者）/ \ n = 1：A规则A（AB→AB），规则（B→A）产生的初始单A A不能应用/ | \ n = 2：A B应用了所有规则的前一个字符串AB，A再次生成为AB，前一个B变为A / | | | \ n = 3：A B A A B请注意，所有A首先生成自己的副本，然后是B，从而将... / | | | \ | \ \ n = 4：将A B A A B A B A ...转化为A一代，然后开始生成/重复/递归

结果是斐波那契单词的序列。如果我们计算每个字符串的长度，则会得到著名的斐波那契数列（由于选择的公理，跳过了前一个1）：

对于每个字符串，如果我们从字符串的左端算起第k个位置，则该值由黄金分割率的倍数是否落入间隔（k − 1，k）{\ displaystyle（k-1 ，k）}。 A对B的比率同样收敛于黄金均值。

如果将规则（A→AB）替换为（A→BA），则本示例将产生相同的结果（就每个字符串的长度而言，不是As和Bs的顺序），只是对字符串进行了镜像。

由于G（n）= G（n-1）G（n-2）{\ displaystyle G（n）= G（n-1）G（n-2）}，其中G（n n）{\ displaystyle G（n）}是第n代。

通过按照生产规则递归地输入公理来构建形状。将对照规则列表检查输入字符串的每个字符，以确定在输出字符串中将其替换为哪个字符或字符串。在此示例中，＆＃39; 1＆＃39;输入字符串中的变为＆＃39; 11＆＃39;在输出字符串中，而＆＃39; [＆＃39;保持不变。将其应用于＆＃39; 0＆＃39;的公理，我们得到：

我们可以看到，该字符串的大小和复杂性迅速增加。可以使用乌龟图形将此字符串绘制为图像，其中为每个符号分配了图形操作以供乌龟执行。例如，在上面的示例中，可以给乌龟以下指示：

推和弹出是指LIFO堆栈（更多的技术语法将对“推位置”和“向左转”使用单独的符号）。当海龟解释遇到＆＃39; [＆＃39;]时，将保存当前位置和角度，然后在解释遇到＆＃39;]时恢复当前位置和角度。如果已推多个值，则＆＃34;然后是＆＃34; pop＆＃34;恢复最近保存的值。将上面列出的图形规则应用于早期的递归，我们得到：

在此，F表示“向前拉”，+表示“向左转90°”，-表示“向右转90°”。 （请参见乌龟图形）。

n = 2：F + 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：F + F-F-F + F + F + F-F-F + F-F + F-F-F + F-F + F-F-F + F + F + F-F- F + F + F + F-F-F + F + F + F-F-F + F-F + F-F-F + FF-F + F-F-F + F + F + F-F-F + F- F + F-F-F + F + F + F-F-F + F-F + F-F-F + FF-F + F-F-F + F + F + F-F-F + F- F + F-F + F + F + F-F-F + F-F + F-F-F + F-F + F-F-F + F + F + F-F-F + F + F + F-F-F + F + F + F-F-F + F-F + F-F-F + F-F + F-F-F + F + F + F-F-F + F 在此，F和G均表示“向前拉”，+表示“向左转角度”，-表示“向右转角度”。 也可以使用Sierpiński箭头曲线L系统近似Sierpinski三角形。

在此，A和B均表示“向前拉”，+表示“向左转角度”，-表示“向右转角度”。 （请参见乌龟图形）。

n = 2，n = 4，n = 6，n = 8的演化这里，F表示＆＃34;向前拉＆＃34 ;， −表示＆＃34;向左转90°＆＃34 ;， +表示＆ ＃34;向右转90°＆＃34;。 X和Y不对应于任何绘制动作，仅用于控制曲线的演变。

n = 10时的龙曲线在此，F表示向前拉＃-表示向右转25°＆＃34； +表示向左转25°＆＃34; 。 X不对应任何绘制动作，并用于控制曲线的演变。方括号＆＃34; [＆＃34;对应于保存位置和角度的当前值，当相应的＆＃34;]＆＃34;被执行。

n = 6的分形工厂已经开发了许多有关此基本L系统技术的技术，可以相互结合使用。其中包括随机语法，上下文相关语法和参数语法。

到目前为止，我们已经讨论的语法模型是确定性的，也就是说，给定语法字母中的任何符号，都会有一个确切的生产规则，该规则总是被选择，并且总是执行相同的转换。一种替代方法是为一个符号指定一个以上的生产规则，并给每个规则指定一个出现的可能性。例如，在示例2的语法中，我们可以更改重写＆＃34; 0＆＃34;的规则。从：

在此生产条件下，每当＆＃34; 0＆＃34;如果在字符串重写过程中遇到该错误，它将有50％的机会如前所述运行，而有50％的机会在生产期间不会更改。当在演化环境中使用随机语法时，建议将随机种子合并到基因型中，以便图像的随机属性在各代之间保持恒定。

上下文相关的生产规则不仅会查看正在修改的符号，还会查看字符串前后的符号。例如，生产规则：

转换＆＃34; a＆＃34;到＆＃34; aa，但只有在＆＃34; a＆＃34;发生在＆＃34; b＆＃34;之间和一个＆＃34; c＆＃34;在输入字符串中：

与随机产品一样，有多种产品可以处理不同上下文中的符号。如果在给定的上下文中找不到生产规则，则假定身份生产，并且符号在转换时不会更改。如果上下文相关的生成和上下文无关的生成都存在于同一语法中，则在适用时将假定上下文相关的生成优先。

在参数语法中，字母表中的每个符号都有与其关联的参数列表。一个符号及其参数列表一起称为模块，参数语法中的字符串是一系列模块。示例字符串可能是：

绘图功能和生产规则都可以使用这些参数。生产规则可以通过两种方式使用参数：第一，在条件语句中确定规则是否将适用；第二，生产规则可以修改实际参数。例如，查看：

如果满足条件x = 0，则模块a（x，y）在该生产规则下进行转换。例如，a（0,2）将进行转换，而a（1,2）将不进行转换。

在生产规则的转换部分，可以影响参数以及整个模块。在上面的示例中，模块b（x，y）使用初始参数（2,3）添加到字符串中。同样，已经存在的模块的参数被转换。根据上述生产规则，

作为＆＃34; x＆＃34; （x，y）的参数显式转换为＆＃34; 1＆＃34;和＆＃34; y＆＃34; a的参数增加1。

参数语法允许通过语法而不是乌龟解释方法来确定线长和分支角。同样，如果将年龄作为模块的参数，则规则可以根据植物段的年龄进行更改，从而可以创建树的整个生命周期的动画。

双向模型将符号重写系统与形状分配明确分开。例如，示例2（分形树）中的字符串重写过程与图形操作如何分配给符号无关。换句话说，无数的绘制方法适用于给定的重写系统。

双向模型包括：1）前向过程使用生产规则构造派生树，以及2）后向过程以逐步的方式（从叶到根）实现具有形状的树。每个逆推导步骤都涉及基本的几何拓扑推理。通过这种双向框架，设计约束和目标被编码在语法形状转换中。在建筑设计应用中，双向语法具有一致的内部连接性和丰富的空间层次结构。 [4]

所有具有确定性的上下文无关L系统的特征，这些L系统是局部链接的。 （仅在只有两个变量的情况下才知道完整的解决方案）。 [5]

^ Lindenmayer，Aristid（1968年3月）。 ＆＃34;开发中细胞相互作用的数学模型。具有两侧输入的单丝和分支丝。理论生物学杂志。 18（3）：300-315。 doi：10.1016 / 0022-5193（68）90080-5。 ISSN 0022-5193。 PMID 5659072。

^ Grzegorz Rozenberg和Arto Salomaa。 L系统的数学理论（Academic Press，纽约，1980年）。国际标准书号（ISBN）0-12-597140-0

^ Hua，H.，2017年12月。建筑设计双向程序模型。在计算机图形学论坛（第36卷，第8期，第219-231页）中。

^卡莉，莱拉；罗岑伯格，格热哥兹； Salomaa，Arto（1997）。 ＆＃34; L Systems＆＃34;。形式语言手册。第253–328页。 doi：10.1007 / 978-3-642-59136-5_5。 ISBN 978-3-642-63863-3。

Grzegorz Rozenberg，Arto Salomaa – Lindenmayer Systems：对理论计算机科学，计算机图形学和发育生物学的影响ISBN 978-3-540-55320-5

D.S.埃伯特（F.K.） Musgrave等。 –纹理和建模：一种程序方法，ISBN 0-12-228730-4

伯里（J. Burry），简（Burry Mark），（2010年）。建筑的新数学，纽约：泰晤士河和哈德森。

阿里斯蒂德·林登马耶（Aristid Lindenmayer），＆＃34;开发过程中细胞相互作用的数学模型。＆＃34; J.定理。生物学，1968：18：280-315。

^ Pradal，克里斯托弗；富尼耶，基督徒；帕特里克·瓦尔杜里兹；莎拉（Cohen-Boulakia），莎拉（2015）。 OpenAlea：科学的工作流程，结合了数据分析和模拟（PDF）。第27届科学与统计数据库管理国际会议论文集-SSDBM＆＃39; 15。 p。 1. doi：10.1145 / 2791347.2791365。 ISBN 9781450337090.S2CID 14246115。

^ Boudon，弗雷德里克；克里斯托弗·普拉达（Pradal）库克勒，托马斯； Prusinkiewicz，Przemyslaw；戈丁，克里斯托夫（2012）。 ＆＃34; L-Py：一种用于基于动态语言对工厂体系结构开发进行建模的L系统仿真框架。植物科学前沿。 3：76. doi：10.3389 / fpls.2012.00076。 PMC3362793。PMID22670147。