L-system

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

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

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

L-system の文法は en:Unrestricted grammar のものに似ている（→ チョムスキー階層）。現在では、以下のような四ツ組によって定義されることが多い。

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-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 を小型の細胞の図などにそれぞれ置き換える）する事で、あたかも寒天培地上に展開した藻類のコロニーのような絵を得る事ができる。

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) で置き換えても同様の数列を得る事ができる。

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）を参照

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

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

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

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

V ： A, B

S ： +, -

ω： A

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

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

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

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

• 草本の作図例：

• 木本の作図例：

• 原生動物など：

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

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

実数列における L-system：

• Thue-Morse sequence

平面における L-system：

• 平面充填曲線・図形（Space-filling curve）ほか：
  • ヒルベルト曲線（Hilbert curve）
  • ペアノ曲線（Peano's curves）
  • コーラム（Kolam）
  • レヴィC曲線（Lévy C curve）
  • ドラゴン曲線（Dragon curve）
  • ペンローズ・タイル（Penrose tiling）

空間における L-system：

• 自然物
  • 植物
    • 木本
    • 草本
    • シダ植物
  • 藻類・原生動物
    • 放散虫

確率的 (Stochastic) L-systemは、L-systemを拡張して確率的に分岐できるようにしたものである。確率的L-systemには標準が無いため、ソフトウェアによって文法が異なる。

以下は確率的な分岐を行うL-systemの実装毎の例である。

A=(0.5)FA
A=(0.25)+F-A
A=(0.25)-F+A

A=FA:0.5
A=+F-A:0.25
A=-F+A:0.25

A:(rnd(1)<0.5)=FA
A:(rnd(1)<0.75)=+F-A
A:(rnd(1)>0.75)=-F+A

文脈依存 (Context-sensitive) L-systemは、L-systemを拡張したものであり、パターンマッチングによって文脈に依存した分岐が可能となっている。文脈依存L-systemを実装したものとしては、Tong Linの実装などが存在する。

ウィキメディア・コモンズには、L-systemに関連するカテゴリがあります。

• フラクタル
  • 反復関数系
  • フラクタル幾何
    • シェルピンスキーのギャスケット
    • コッホ曲線
• 先端成長

• Przemyslaw Prusinkiewicz - en:The Algorithmic Beauty of Plants PDF version available here for free

• David J. Wright's article on L-systems
• Algorithmic Botany at the University of Calgary
• Branching: L-system Tree L-systemを用いて木の生長をシミュレートするJavaアプレット（英語）
• 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-system in Falk arts" The FORMA commurative issue of the conference ISKFA06
• A simple L-systems generator (Windows)
• Lyndyhop: another simple L-systems generator (Windows & Mac)
• An evolutionary L-systems generator (anyos*)
• L-systems gallery – a tribute to Fractint
• "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.
• 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.
• LSys/JS - Interactive L-System interpreter using the Canvas HTML element.

表 話 編 歴 フラクタル
特徴	フラクタル次元 Assouad（英語版） Box-counting（英語版） Correlation（英語版） ハウスドルフ Packing（英語版） 位相 再帰（英語版） 自己相似 自己相似過程 スケール不変性
反復関数系	バーンズリーのシダ カントール集合 ドラゴン曲線 レヴィC曲線 コッホ雪片 メンガーのスポンジ シェルピンスキーのカーペット シェルピンスキーの三角形 空間充填曲線 T-square（英語版）
ストレンジアトラクター	多重フラクタル系（英語版）
L-system	空間充填曲線
Escape-time fractals	バーニングシップ・フラクタル ジュリア集合 充填 リアプノフ・フラクタル マンデルブロ集合 ニュートン・フラクタル（英語版）
確率的フラクタル	ブラウン運動 非整数ブラウン運動 ブラウンの木（英語版） 拡散律速凝集 フラクタル地形 Lévy flight（英語版） パーコレーション理論（英語版） Self-avoiding walk（英語版）
人物	ゲオルク・カントール フェリックス・ハウスドルフ ガストン・ジュリア ヘルゲ・フォン・コッホ ポール・レヴィ アレクサンドル・リャプノフ ブノワ・マンデルブロ ルイス・フライ・リチャードソン ヴァツワフ・シェルピニスキ
その他	"How Long Is the Coast of Britain?（英語版）" 海岸線のパラドックス List of fractals by Hausdorff dimension（英語版） The Beauty of Fractals（英語版） (1986 book)
カテゴリ