L-系统

**Lindenmayer 系統**，簡稱 **L 系統**，是由荷蘭烏特勒支大學的生物學和植物學家，匈牙利裔的林登麥伊爾（Aristid Lindenmayer）於 1968 年提出的有關生長發展中的細胞交互作用的數學模型，尤其被廣泛應用於植物生長過程的研究。

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 文法。

## 參考文獻

## 外部連結

* David J. Wright's article on L-systems
* Algorithmic Botany at the University of Calgary （頁面存檔備份，存於網際網路檔案館）
* Branching: L-system Tree （頁面存檔備份，存於網際網路檔案館）　A Java applet of the botanical tree growth simulation using the L-system.
* Fractint L-System True Fractals
* "An introduction to Lindenmayer systems", by Gabriela Ochoa。Brief description of L-systems and how the strings they generate can be interpreted by computer.
* "powerPlant" an open-source landscape modelling software （頁面存檔備份，存於網際網路檔案館）
* _Fractint_ home page
* L-Systems in Architecture （頁面存檔備份，存於網際網路檔案館）
* A simple L-systems generator (Windows)
* Lyndyhop: another simple L-systems generator (Windows & Mac)
* An evolutionary L-systems generator (anyos\*) （頁面存檔備份，存於網際網路檔案館）
* "LsystemComposition". 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. （頁面存檔備份，存於網際網路檔案館）
* Another L-system applet, supporting programming, with explanation and examples.
* L-systems in Architecture; genetic housing.
* 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. （頁面存檔備份，存於網際網路檔案館）
* L-system digital sound synthesis: 'Do Digital Monkeys Inhabit Virtual Trees?' Electronic music piece composed with L-systems.
* LSys/JS - Interactive L-System interpreter using the Canvas HTML element。
* Lindenmayer System for plant visualisation (Java Applet)。
* 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
* Garabatos，an interactive evolutionary image generator based in L-Systems
* Online experiments with L-Systems using JSXGraph (JavaScript) （頁面存檔備份，存於網際網路檔案館）

## 參見

* 碎形
* 迭代函數系統
* 希爾伯特曲線
* 圖靈機
* 圖靈歸約
* 交互式證明系統
* 隨機預言機