L-system

L-system（エルシステム）とは

L-system、あるいはリンデンマイヤーシステムは、ハンガリー出身でユトレヒト大学に所属していた理論生物学者および植物学者、アリステッド・リンデンマイヤーによって1968年に提唱された形式文法の一種です。これは、特に植物の成長プロセスをはじめとする様々な自然界に存在する構造を記述し、表現するためのアルゴリズムとして開発されました。

自然物のモデリングだけでなく、反復関数系（IFS）によって生み出されるような、いわゆる自己相似図形やフラクタル図形を生成する際にも広く利用されています。

誕生の背景

リンデンマイヤーは生物学者として、酵母や糸状菌、特定の藻類（例：Anabaena catenula）といった様々な生物の成長パターンに深い関心を寄せていました。L-systemは当初、こうした単細胞生物や比較的構造が単純な多細胞生物の成長様式、そして植物細胞間における相互作用を記述するために考案されました。その後、このシステムはさらに発展を遂げ、より複雑な形態を持つ高等植物や、樹木の枝分かれのような複雑な分岐構造を表現するための強力なツールへと進化していきました。

L-systemの仕組み

L-systemの根本原理は「再帰性」にあります。この再帰的な性質により、自己相似性を持つ図形やフラクタル図形のような形状を比較的容易に記述できます。また、植物やその他の生物が持つ、自然で有機的な見た目の構造もシンプルに定義することが可能です。システムの反復計算（「世代」を重ねるごとに相当）を増やすことで、あたかも構造が「成長」し、次第に複雑になっていく様子を視覚的に表現できます。この特性から、L-systemは人工生命の分野でも頻繁に用いられます。

L-systemの文法構造は、チョムスキー階層における非制限文法（Unrestricted grammar）に類似しています。現在では、多くの場合、以下の四つの要素からなる組として定義されます。

G = {V, S, ω, P}

各要素の意味は以下の通りです。

V（変数、またはアルファベット）: これは、置換規則（後述のP）に従って繰り返し置き換えられていく記号の集合です。L-systemの計算が進むにつれて、「成長」していく文字列は、このVの要素から構成されます。
S（定数）: 計算の過程で変化することのない記号の集合です。
ω（初期状態、または公理）: システムの計算を開始する際の最初の文字列であり、Vの要素からなります。
P（置換規則、またはプロダクション）: Vに含まれる記号を他の文字列に置き換えるための規則の集合です。各規則は、例えば `(A → AB)` のように、置き換えられる対象の記号と、それに置き換わる文字列のペアとして記述されます。

置換規則Pにおいて、置き換えの対象が単一の記号のみである場合、生成される言語は文脈自由言語となります。一方、置換規則が置き換え対象の記号だけでなく、その周囲（文脈）にある記号との関係を考慮して適用される場合、生成される言語は文脈依存言語となります。また、置換規則Pが各記号に対して常に確実に適用される場合、そのL-systemは「決定論的」と呼ばれ、特に文脈自由で決定論的なものはD0L-system（deterministic context-free L-system）などと称されます。対照的に、規則の適用が確率的に行われるものは「確率論的L-system」と呼ばれます。

L-systemをコンピュータグラフィックスに応用する場合、生成された文字列を画面上の図形描画コマンドに変換する必要があります。例えば、タートルグラフィックスという手法では、L-systemの文字列を「タートル（仮想的な描画ロボット）」に対する「前進」「回転」といった命令に翻訳し、図形を描画させます。

L-systemの応用例

L-systemは様々な構造を表現できます。いくつかの代表例を見てみましょう。

藻類の成長: L-system開発のきっかけとなった例です。単純な規則 `(A → AB), (B → A)` （Aが分裂可能な細胞、Bが未熟な細胞を表すなど）から、世代を重ねるごとに `A`, `AB`, `ABA`, `ABAAB`, `ABAABABA`... と文字列が変化し、藻類のコロニーのような成長パターンをモデル化できます。
フィボナッチ数列: 規則 `(A → B), (B → AB)` から始まる文字列 `A`, `B`, `AB`, `BAB`, `ABBAB`... の各世代の文字列長が、フィボナッチ数列（1, 1, 2, 3, 5, ...）になる例です。
カントール集合: 規則 `(A → ABA), (B → BBB)` （Aが線分、Bが除去部分）を用いると、世代ごとに線分を3分割して中央を取り除く操作が繰り返され、フラクタル図形であるカントール集合の構造を表現できます。
コッホ曲線: タートルグラフィックスと組み合わせて用いられます。例えば、前進をF、左・右回転を+・-とし、規則を `(F → F+F-F-F+F)` とすると、世代を重ねるごとに複雑なコッホ曲線のパスが生成されます。
シェルピンスキーの三角形: 規則 `(A → B−A−B), (B → A+B+A)` （A, Bは描画、+は左60°回転、-は右60°回転）を用いることで、フラクタル図形であるシェルピンスキーの三角形を描くことができます。
その他の応用: ペンローズ・タイルのような平面充填模様、様々な種類の植物（草本、木本、シダ）、原生動物など、幅広い自然物や抽象的な図形の生成に利用されています。

L-systemの種類と課題

L-systemには、実数列、平面、空間といった異なる次元での応用があり、ヒルベルト曲線、ペアノ曲線、ドラゴン曲線、ペンローズ・タイルなど、多様なフラクタルや空間充填曲線を生成する能力を持っています。

また、基本形以外にも、規則適用を確率的に行う確率的L-systemや、隣接する記号を考慮して規則を適用する文脈依存L-systemといった拡張も存在します。

L-systemには多くの利点がありますが、既知の課題も存在します。その一つは、「逆問題」の難しさです。これは、ある特定の構造や画像が与えられたときに、それを生成するためのL-systemの規則や初期状態を自動的に見つけ出すことが非常に困難であるという問題です。特に、自然物のように複雑で多くの反復を経て形成された構造では、この課題が顕著になります。

L-systemは、シンプルな規則から驚くほど多様で複雑な構造を生み出すことができる、生物学と計算科学を結びつける興味深いアルゴリズムであり、現在も様々な分野で研究・応用が応用されています。

もう一度検索