L-system

出典: フリー百科事典『ウィキペディア（Wikipedia）』

L-system（エルシステム、Lindenmayer system）は形式文法の一種で、植物の成長プロセスを初めとした様々な自然物の構造を記述・表現できるアルゴリズムである。自然物の他にも、反復関数系（Iterated Function System; IFS）のようないわゆる自己相似図形やフラクタル図形を生成する場合にも用いられる。L-System は1968年、ハンガリーユトレヒト大学の理論生物学者にして植物学者であったアリステッド・リンデンマイヤー（Aristid Lindenmayer）により提唱され、発展した。

[編集] 起源

L-system により生成された3次元の樹木モデル。

生物学者としてリンデンマイヤーは、酵母や糸状菌、そして藍藻類の Anabaena catenula のような藻類など、様々な生物の成長パターンを研究していた。もともと L-system は、そのような単細胞生物もしくは体制の単純な多細胞生物の成長様式や、植物細胞における近隣の細胞の相互関係を記述するために開発されたものであった。後に L-system はより高等な植物の形態や、複雑な分岐構造を記述する為のツールとして発展を遂げるのである。

[編集] L-system の構造

L-system の基本は再帰性で、自己相似図形やフラクタル図形のような形状を簡単に記述する事ができる。植物やその他の見た目が自然な生物構造も同様に簡単に定義でき、再帰呼出の回数を増やす事であたかも構造が「成長」し、複雑化していくように見える。L-system は人工生命の生成にもよく用いられる。

L-system の文法は semi-Thue grammar のものに似ている（→ チョムスキー階層）。現在では、L-system は下記のようなタプルとして定義される「パラメトリック L-system」として一般に知られている。

G = {V, S, ω, P},

上記において、各要素は以下の意味を持つ。

V（文字）：置換規則（後述の P ）により順次置き換えられてゆく変数。L-system の再帰的な反復計算が進んでいく時に、物として「成長」してゆくのはこの V で定義された文字の文字列である。
S ：計算が進んでも変化しない定数。
ω ： V の初期状態。
P ： V を変化させてゆく置換規則。例えば (A → AB) のように、置換前（置換対象）の文字列と置換後の文字列の組み合わせにより記述される。

置換規則 P において、置換対象が単独の文字のみである場合、L-system は文脈自由言語である。一方、置換規則が近隣の文字との相互関係まで考慮するものである場合、L-system は文脈依存言語である。また、置換規則Pが各文字に対して毎回確実に適用される時、L-system は「決定論的」であると言われ、D0L-system（deterministic context-free L-system ）などと呼ばれる。逆に、置換規則の適用が確率に左右される場合には「確率論的」L-system と呼ばれる。

L-system をグラフィックスに応用する場合、L-system が生成する文字列を、何らかの形で画面上の図形に変換しなければならない。例えば FractInt というプログラム（文末の外部リンク参照）では、LOGOのようなタートルを利用してグラフィックスを生成する。つまりプログラムが L-system の文字列をタートルの制御命令に翻訳し、図形を描画させているのである。

[編集] L-systems の実例

[編集] 例1：藻類

L-system 誕生の契機となった、藻類の成長を記述する例。

V ： A, B

S ：なし

ω： A

P ： (A → AB), (B → A)

順次計算してゆくと、文字列は以下のように成長する。

n = 0 ： A

n = 1 ： AB

n = 2 ： ABA

n = 3 ： ABAAB

n = 4 ： ABAABABA

この例では、置換規則 P において、(A → AB) は不均等な細胞分裂により通常の細胞Aと未熟な細胞Bが生じる事を表し、(B → A) は未熟な細胞Bが成長して分裂可能な細胞 A へと成熟する事を表している。この文字列を図形化（例えば A を分枝型の細胞、B を小型の細胞の図などにそれぞれ置き換える）する事で、あたかも寒天培地上に展開した藻類のコロニーのような絵を得る事ができる。

[編集] 例2：フィボナッチ数列

V ： A, B

S ：なし

ω： A

P ： (A → B), (B → AB)

計算を進めると、以下のような文字列となる。

n = 0 ： A

n = 1 ： B

n = 2 ： AB

n = 3 ： BAB

n = 4 ： ABBAB

n = 5 ： BABABBAB

n = 6 ： ABBABBABABBAB

n = 7 ： BABABBABABBABBABABBAB

この文字列の各文字数を n=0 から順に数えると、フィボナッチ数列（1 1 2 3 5 8 13 21 34 55 89 …）となっている。この例では文字列の内容は問わず長さだけに注目しているので、例えば置換規則の (B → AB) を (B → BA) で置き換えても同様の数列を得る事ができる。

[編集] 例3：カントール集合

V ： A, B

S ：なし

ω： A

P ： (A → ABA), (B → BBB)

計算を進めると、以下のような文字列となる。

n = 0 ： A

n = 1 ： ABA

n = 2 ： ABABBBABA

n = 3 ： ABABBBABABBBBBBBBBABABBBABA

この文字列の A を線分、B を抜き取られた部分に置き換えると下のような図が得られる。置換規則の (A → ABA) は線分（閉区間）を3等分して中央を抜き取る操作に相当する。(B → BBB) は一度取り除かれた区間が戻らない事を意味する。詳しくはカントール集合（Cantor set）を参照

[編集] 例4：コッホ曲線

直角で構成されるコッホ曲線の描画例。

V ： F

S ： +, -;

ω： F

P ： (F → F+F-F-F+F)

上記において、F はタートルによる直線の描画、+ はタートルを左へ90°回転、同じく- は右へ90°回転する事を意味する。これを順次計算すると、以下のような図形が得られる。

n = 0 ：

F

n = 1 ：

F+F-F-F+F

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+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

[編集] 例5：ペンローズ・タイル

L-system を利用して、下図のような平面充填模様を生成する事もできる。詳しくはペンローズ・タイル及びロジャー・ペンローズを参照。

[編集] 例6：シェルピンスキーの三角形

L-system でシェルピンスキーの三角形を作図する例。

V ： A, B

S ： +, -

ω： A

P ： (A → B−A−B), (B → A+B+A)

上記において、A 及び B はタートルによる直線の描画、+ はタートルを左へ60°回転、同じく- は右へ60°回転する事を意味する。同様の図形を描く置換規則は他にもあるが、この規則の場合、タートルは三角形の左下から描き始める事になる。

n = 2, n = 4, n = 6, n = 9 の時にそれぞれ描画される図形。n → ∞ の時、シェルピンスキーの三角形に等しくなる。

[編集] 例7：コッホ曲線の変形

通常のコッホ曲線に、周期的な角度の変更を加えながら描画したフラクタル図形の一種。

[編集] その他の L-system を利用したグラフィックス

地衣類、あるいは蘚苔類：

草本の作図例：

木本の作図例：

原生動物など：

（参考）ヘッケルによる放散虫のスケッチ。

[編集] 既知の問題

L-system に関する問題は数多く存在するが、その最たるものは L-system を逆に辿る事が困難であるというものである。具体的には、ある構造が示された時に、その構造を生成するパラメータや置換規則を見つける事が難しい。これは自然物のような複雑な（反復回数の多い）過程を経て形成された図形に顕著である。