L-system

# L系统 来源：https://en.wikipedia.org/wiki/L-system  L系统树木形成自然图案的真实模型 **L系统**或**林登迈耶系统**是一种[并行](https://en.wiktionary.org/wiki/parallel)[重写系统](https://en.wikipedia.org/wiki/Rewriting_system)，也是[形式文法](https://en.wikipedia.org/wiki/Formal_grammar)的一种。L系统由一个符号[字母表](https://en.wikipedia.org/wiki/Alphabet)（这些符号可用于构成[字符串](https://en.wikipedia.org/wiki/String_(computer_science))）、一组[产生式规则](https://en.wikipedia.org/wiki/Production_(computer_science))（每条规则将一个符号扩展为更大的符号串）、一个初始的“[公理](https://en.wikipedia.org/wiki/Axiom)”字符串（用于开始构造）以及一种将生成的字符串转化为几何结构的机制组成。L系统由匈牙利理论生物学家和植物学家[阿里斯蒂德·林登迈耶](https://en.wikipedia.org/wiki/Aristid_Lindenmayer)于1968年在[乌得勒支大学](https://en.wikipedia.org/wiki/Utrecht_University)提出并发展[[1]](https://en.wikipedia.org/wiki/L-system#cite_note-1)。林登迈耶利用L系统描述植物细胞的行为，并对[植物发育](https://en.wikipedia.org/wiki/Plant_development)的生长过程进行建模。L系统也被用于模拟多种生物的形态[[2]](https://en.wikipedia.org/wiki/L-system#cite_note-2)，并能生成自相似的[分形](https://en.wikipedia.org/wiki/Fractal)。  使用L系统在3D中生成的“杂草” 作为一名生物学家，林登迈耶曾研究[酵母](https://en.wikipedia.org/wiki/Yeast)和丝状[真菌](https://en.wikipedia.org/wiki/Fungi)，并探究多种[细菌](https://en.wikipedia.org/wiki/Bacteria)（如蓝细菌*Anabaena catenula*）的生长模式。最初，L系统旨在为这类简单多细胞生物的发育提供形式化描述，并展现植物细胞之间的邻域关系。后来，该系统被扩展用于描述高等植物和复杂的分支结构。L系统规则的[递归](https://en.wikipedia.org/wiki/Recursion)特性导致了[自相似性](https://en.wikipedia.org/wiki/Self-similarity)，因此容易用L系统描述[分形](https://en.wikipedia.org/wiki/Fractal)般的形态。植物模型和自然逼真的有机形态很容易定义，随着递归层次的增加，形态缓慢“生长”并变得更加复杂。林登迈耶系统在[人工生命](https://en.wikipedia.org/wiki/Artificial_life)生成中也很受欢迎。L系统文法与[半图厄文法](https://en.wikipedia.org/wiki/Semi-Thue_grammar)（参见[乔姆斯基层级](https://en.wikipedia.org/wiki/Chomsky_hierarchy)）非常相似。 现在通常所说的*参数化*L系统定义为[元组](https://en.wikipedia.org/wiki/Tuple) **G** = ( *V* , ω, *P* )，其中 - **V**（*字母表*）是一个符号集合，包含可被替换的元素（*变量*）和不可被替换的元素（“常量”或“终结符”） - **ω**（*起始符*、*公理*或*初始符*）是由 **V** 中符号组成的字符串，定义了系统的初始状态 - **P** 是一组[产生式规则](https://en.wikipedia.org/wiki/Production_(computer_science))（或产生式），定义了变量如何被常量和其他变量的组合替换。一个产生式由两个字符串组成：*前驱*和*后继*。对于集合 V 中任何不在 P 中任何产生式左侧出现的符号 A，假定恒等产生式 A → A；这些符号称为*常量*或*终结符*（参见[同一律](https://en.wikipedia.org/wiki/Law_of_identity)）。 L系统文法的规则从初始状态开始迭代应用。每次迭代中，尽可能多的规则被同时应用。每次迭代应用尽可能多的规则这一事实，将L系统与由[形式文法](https://en.wikipedia.org/wiki/Formal_grammar)生成的[形式语言](https://en.wikipedia.org/wiki/Formal_language)区分开来——形式文法每次只应用一条规则。如果每次只应用一条产生式规则，那么只是简单地生成语言中的一个字符串，而所有这样的应用序列将产生该文法指定的语言。然而，某些语言中的一些字符串如果将该文法视为L系统（而非语言规范）则无法生成。例如[[3]](https://en.wikipedia.org/wiki/L-system#cite_note-3)，假设文法中有一条规则 S→SS。如果一次只应用一条产生式，那么从S开始，我们首先得到SS，然后再次应用规则得到SSS。然而，如果像L系统那样在每个步骤应用所有适用的规则，则无法得到这种句形式。相反，第一步会得到SS，但第二步会应用两次规则，得到SSSS。因此，由给定文法产生的L系统字符串集合是文法所定义的形式语言的子集；如果我们将语言定义为一组字符串，这意味着给定的L系统实际上是L系统文法所定义的形式语言的子集。 如果每条产生式规则仅涉及单个符号而不涉及其邻居，则L系统是*上下文无关*的。上下文无关L系统由[上下文无关文法](https://en.wikipedia.org/wiki/Context-free_grammar)指定。如果规则不仅依赖于单个符号，还依赖于其邻居，则称为*上下文相关*L系统。如果每个符号恰好有一个产生式，则L系统是*确定性的*（确定性上下文无关L系统常被称为*D0L系统*）。如果有多个产生式且每次迭代以一定概率选择其一，则为*随机*L系统。 使用L系统生成图形图像要求模型中的符号对应计算机屏幕上的绘图元素。例如，*Fractint*程序使用[turtle图形](https://en.wikipedia.org/wiki/Turtle_graphics)（类似于[Logo编程语言](https://en.wikipedia.org/wiki/Logo_programming_language)中的图形）来生成屏幕图像。它将L系统模型中的每个常量解释为一条turtle命令。 ## L系统的示例 [编辑](https://en.wikipedia.org/w/index.php?title=L-system&action=edit§ion=3) 林登迈耶用于模拟藻类生长的原始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：藻类，解释 [编辑](https://en.wikipedia.org/w/index.php?title=L-system&action=edit§ion=5) ``` n=0: A 开始 (公理/初始符) / \ n=1: A B 初始单个A通过规则(A→AB)生成AB，规则(B→A)无法应用 /| \ n=2: A B A 先前字符串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，开始生成/重复/递归 ``` 结果是[斐波那契词](https://en.wikipedia.org/wiki/Fibonacci_word)序列。若计算每个字符串的长度，得到[斐波那契数列](https://en.wikipedia.org/wiki/Fibonacci_sequence)（跳过第一个1，由于公理的选择）：1 2 3 5 8 13 21 34 55 89 ... 若不想跳过第一个1，可使用公理 *B*。这将在上述图表的顶层节点 (*A*) 之前放置一个 *B* 节点。对于每个字符串，如果从字符串左端数起第 *k* 个位置的值，由[黄金比例](https://en.wikipedia.org/wiki/Golden_ratio)的倍数是否落在区间 {\displaystyle (k-1,k)} 内决定。A与B的比例也收敛于黄金均值。若将规则 (*A* → *AB*) 替换为 (*A* → *BA*) 得到相同的结果（以每个字符串的长度而言，而非*A*和*B*的序列），只是字符串互为镜像。该序列是[局部连接序列](https://en.wikipedia.org/wiki/Locally_catenative_sequence)，因为 {\displaystyle G(n)=G(n-1)G(n-2)}，其中 {\displaystyle G(n)} 是第 *n* 代。 ### 示例2：分形（二叉）树 [编辑](https://en.wikipedia.org/w/index.php?title=L-system&action=edit§ion=6) - **变量**：0, 1 - **常量**："["，"]" - **公理**：0 - **规则**：(1 → 11)，(0 → 1[0]0) 通过[递归](https://en.wikipedia.org/wiki/Recursion)地将公理输入产生式规则来构建形状。输入字符串中的每个字符与规则列表匹配，以确定输出字符串中替换为何字符或字符串。在此示例中，输入字符串中的'1'在输出字符串中变成'11'，而'['保持不变。将其应用于公理'0'，得到： 公理：0 第1次递归：1[0]0 第2次递归：11[1[0]0]1[0]0 第3次递归：1111[11[1[0]0]1[0]0]11[1[0]0]1[0]0 ... 可以看出该字符串迅速增长，变得复杂。这个字符串可以用[turtle图形](https://en.wikipedia.org/wiki/Turtle_graphics)绘制成图像，其中每个符号被赋予一个图形操作供turtle执行。例如，在上述示例中，turtle可被赋予以下指令： - 0：画一条[线段](https://en.wikipedia.org/wiki/Line_segment)并以叶片结束 - 1：画一条线段 - [：推入位置和角度，左转45度 - ]：弹出位置和角度，右转45度 推入和弹出指的是[LIFO](https://en.wikipedia.org/wiki/LIFO_(computing))栈（更技术性的文法会有单独的符号用于“推入位置”和“左转”）。当turtle解释遇到'[‘时，当前的位置和角度被保存，当遇到']'时恢复。如果多个值被“推入”，则“弹出”恢复最近保存的值。将上述图形规则应用于前面的递归，得到： - [公理](https://en.wikipedia.org/wiki/File:Graftal0.png) 公理 - [第一次递归](https://en.wikipedia.org/wiki/File:Graftal1.png) 第一次递归 - [第二次递归](https://en.wikipedia.org/wiki/File:Graftal2.png) 第二次递归 - [第三次递归](https://en.wikipedia.org/wiki/File:Graftal3.png) 第三次递归 - [第四次递归](https://en.wikipedia.org/wiki/File:Graftal4.png) 第四次递归 - [第七次递归，缩小十倍](https://en.wikipedia.org/wiki/File:Graftal7.png) 第七次递归，缩小十倍 ### 示例3：康托集 [编辑](https://en.wikipedia.org/w/index.php?title=L-system&action=edit§ion=7)  **变量**：A B **常量**：无 **起始**：A {起始字符序列} **规则**：(A → ABA)，(B → BBB) 令*A*表示“向前画线”，*B*表示“向前移动”。这产生了实数直线**R**上著名的[康托尔分形集](https://en.wikipedia.org/wiki/Cantor_set)。 ### 示例4：科赫曲线 [编辑](https://en.wikipedia.org/w/index.php?title=L-system&action=edit§ion=8) 仅使用直角的[科赫曲线](https://en.wikipedia.org/wiki/Koch_snowflake)变体。 **变量**：F **常量**：+ − **起始**：F **规则**：(F → F+F−F−F+F) 此处，F表示“向前画线”，+表示“左转90°”，−表示“右转90°”（参见[turtle图形](https://en.wikipedia.org/wiki/Turtle_graphics)）。 *n* = 0：F [科赫正方形 - 0次迭代](https://en.wikipedia.org/wiki/File:Square_koch.svg) *n* = 1：F+F−F−F+F [科赫正方形 - 1次迭代](https://en.wikipedia.org/wiki/File:Square_koch_1.svg) *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 [科赫正方形 - 2次迭代](https://en.wikipedia.org/wiki/File:Square_koch_2.svg) *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+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 [科赫正方形 - 3次迭代](https://en.wikipedia.org/wiki/File:Square_koch_3.svg) ### 示例5：谢尔宾斯基三角形 [编辑](https://en.wikipedia.org/w/index.php?title=L-system&action=edit§ion=9) 使用L系统绘制的[谢尔宾斯基三角形](https://en.wikipedia.org/wiki/Sierpinski_triangle)。 **变量**：F G **常量**：+ − **起始**：F−G−G **规则**：(F → F−G+F+G−F)，(G → GG) **角度**：120° 此处，F和G均表示“向前画线”，+表示“左转角度”，−表示“右转角度”。 - [n = 2](https://en.wikipedia.org/wiki/File:Sierpinski_Triangle_(from_L-System,_2_iterations).png) n = 2 - [n = 4](https://en.wikipedia.org/wiki/File:Sierpinski_Triangle_(from_L-System,_4_iterations).png) n = 4 - [n = 6](https://en.wikipedia.org/wiki/File:Sierpinski_Triangle_(from_L-System,_6_iterations).png) n = 6 也可以使用[谢尔宾斯基箭头曲线](https://en.wikipedia.org/wiki/Sierpi%C5%84ski_arrowhead_curve)L系统来近似[谢尔宾斯基三角形](https://en.wikipedia.org/wiki/Sierpinski_triangle)。 **变量**：A B **常量**：+ − **起始**：A **规则**：(A → B−A−B)，(B → A+B+A) **角度**：60° 此处，A和B均表示“向前画线”，+表示“左转角度”，−表示“右转角度”（参见[turtle图形](https://en.wikipedia.org/wiki/Turtle_graphics)）。  *n* = 2, *n* = 4, *n* = 6, *n* = 8的演化 ### 示例6：龙形曲线 [编辑](https://en.wikipedia.org/w/index.php?title=L-system&action=edit§ion=10) 使用L系统绘制的[龙形曲线](https://en.wikipedia.org/wiki/Dragon_curve)。 **变量**：F G **常量**：+ − **起始**：F **规则**：(F → F+G)，(G → F−G) **角度**：90° 此处，F和G均表示“向前画线”，+表示“左转角度”，−表示“右转角度”。  *n* = 10的龙形曲线 ### 示例7：分形植物 [编辑](https://en.wikipedia.org/w/index.php?title=L-system&action=edit§ion=11) **变量**：X F **常量**：+ − [ ] **起始**：−X **规则**：(X → F+[[X]−X]−F[−FX]+X)，(F → FF) **角度**：25° 首先需要初始化一个空栈。这遵循LIFO（后进先出）方法添加和删除元素。此处，F表示“向前画线”，−表示“右转25°”，+表示“左转25°”。X不对应任何绘图动作，用于控制曲线的演化。方括号“[”表示保存当前位置和角度，因此位置和角度被推入栈顶；当遇到“]”符号时，栈被弹出，位置和角度被重置。每个“[”都出现在每个“]”之前。   *n* = 6的分形植物