L系統

L－系統是匈牙利生物學家Aristid LinderMayer於1968年提出的。.L－系統的本質是一個重寫系統，通過對植物對象生長過程的經驗式概括和抽象，初始狀態與描述規則，進行有限次疊代，生成字元發展序列以表現植物的拓撲結構，並對產生的字元串進行幾何解釋，就能生成非常複雜的分形圖形。

基本介紹

• 中文名：L－系統
• 本質：重寫系統
• 提出：Aristid LinderMayer
• 時間：1968年

詳細介紹

一類動態細胞自動機，在每一（時間）步上，其中的各個細胞可以由給定狀態變為一個新的狀態，或消亡或分裂為具有某種狀態組合的細胞串。A.林頓梅伊爾曾用這種細胞自動機描述絲狀有機體的發育過程，所以叫作林頓梅伊爾系統，簡稱L系統。

在喬姆斯基形式語言理論中，字母表被分成終結字母表和非終結字母表部分，“字”是由終結字母組成的字母序列。在L系統中，沒有單獨的終結字母表,所有生成的字都在系統語言中；初始字母可以被初始字所代替；被注視的字所包含的各個字母同時進行改寫。每個字母代表一個細胞，用字表示細胞陣列發展的階段。生成式對應於發展指令，這些指令的套用使有機體生長成已知類型。消亡的細胞可以用空字 e表示。細胞之間可以有，也可以沒有互動作用（信息傳遞）。有互動作用的有1L系統和2L系統。沒有互動作用的叫作0L系統。

0L系統是一個三元組Γ=(G，g，δ),其中G為一個有限非空集合，叫作字母表；g為G中元素的非空序列，即非空字；δ為一個(轉移)函式，首先取作從G到G*（G中元素所能構成的一切序列的集合）的有限非空子集的映射。然後,把δ擴充為從G*到G*的有限非空子集的映射。

如果空字e不能替換任何字母，即對 G中所有字母ɑ，都有e唘δ(ɑ)，就稱Γ為增殖0L系統，簡稱P0L系統；如果對字母表內每一個字母有且只有一個轉移規則，即對G中所有ɑ，在G*中只有一個字p使δ(ɑ)={p}，就稱Γ為確定的0L系統，簡稱 D0L系統。顯然（P0L∪D0L）吇0L。而既增殖又確定的DL系統稱為DP0L。

L系統舉例

設C=（G、g、δ），且其中(·)表示分枝,│表示細胞間直壁,/為斜壁(不分左傾或右傾),取初始字g=4,G和δ由表給出。終極字母集合T={3,(·),│,/}。轉移規則(1→3│2)表示每個處於狀態1的細胞到下一時刻分裂成為分別處於狀態 3和2由一個直壁隔開的兩個新細胞;（2→3(4)）意思是處於狀態2的細胞，下一時刻分裂成為一個處於狀態3的細胞和一個以它為基部分枝後處於狀態4的細胞。這是一個DP0L系統。由這個系統C能生成字的無窮序列,即L(C)。開頭的六個字和它們的圖解如下：

公式

定義：三元組<v,w,p>其中

公式

v——表示字母集合

v*——表示v上所有單詞的集合

w——是一個非空單詞，稱為公理

p——產生式集合 任取α∈V，存在x∈v* 使得 α→x 如果沒有明顯是產生式，則令α→α

具體例子如下：雪花曲線

v：{F,+, - }

雪花系統

w：F

p：F->F-F++F-F

幾何解釋是：

F：向前畫一條線

+：右轉67.5度（++即為右轉135度）

-：左轉45度

具體信息見右圖，當疊代次數n=3時就可以得出很好的雪花形狀，