泛系理論

[拼音]：L xitong

[英文]：L system

一類動態細胞自動機，在每一（時間）步上，其中的各個細胞可以由給定狀態變為一個新的狀態，或消亡或分裂為具有某種狀態組合的細胞串。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)。開頭的六個字和它們的圖解如