Lシステム

L システムまたはリンデンマイヤー システムは、並列書き換えシステムであり、形式文法の一種です。L システムは、文字列の作成に使用できる記号のアルファベット、各記号をより大きな記号の文字列に展開する生成規則のコレクション、構築を開始するための最初の「公理」文字列、および生成された文字列を幾何学的構造に変換するメカニズムで構成されます。L システムは、1968 年にハンガリーの理論生物学者でユトレヒト大学の植物学者であるアリスティド リンデンマイヤーによって導入され、開発されました。^[1]リンデンマイヤーは、L システムを使用して植物細胞の挙動を記述し、植物の発達の成長プロセスをモデル化しました。L システムは、さまざまな生物の形態をモデル化するためにも使用されており^{[2] 、自己相似}フラクタルを生成するために使用できます。

生物学者として、リンデンマイヤーは酵母と糸状菌を研究し、シアノバクテリアのアナベナ・カテヌラなど、さまざまな種類の細菌の成長パターンを研究しました。もともと、Lシステムは、そのような単純な多細胞生物の発達の正式な説明を提供し、植物細胞間の近隣関係を示すために考案されました。後に、このシステムは高等植物と複雑な分岐構造を説明するために拡張されました。

L システム ルールの再帰的な性質により自己相似性が生じ、フラクタルのような形状を L システムで簡単に記述できます。再帰レベルを上げると形状がゆっくりと「成長」し、より複雑になるため、植物モデルや自然に見える有機形状を簡単に定義できます。リンデンマイヤー システムは人工生命の生成でも人気があります。

Lシステム文法はセミThue文法（チョムスキー階層を参照）と非常によく似ている。Lシステムは現在、パラメトリックLシステムとして知られており、タプルとして定義される。

G = ( V , ω , P )、

どこ

• V（アルファベット）は、置換可能な要素（変数）と置換不可能な要素（「定数」または「端子」）の両方を含む記号のセットです。
• ω (開始、公理、または開始者) は、システムの初期状態を定義するVからの一連の記号です。
• P は、変数を定数と他の変数の組み合わせで置き換える方法を定義する生成規則または生成規則のセットです。生成規則は、先行文字列と後続文字列の 2 つの文字列で構成されます。集合 V のメンバーであり、P の生成規則の左側に現れない任意のシンボル A については、恒等生成規則 A → A が想定されます。これらのシンボルは、定数または終端記号と呼ばれます。(恒等法則を参照)。

L システム文法の規則は、初期状態から開始して反復的に適用されます。反復ごとに、可能な限り多くの規則が同時に適用されます。各反復で可能な限り多くの規則が使用されるという事実は、反復ごとに 1 つの規則のみを適用する形式文法によって生成された形式言語と L システムとを区別します。生成規則が一度に 1 つだけ適用される場合、言語で文字列が生成され、そのようなすべての適用シーケンスによって、文法で指定された言語が生成されます。ただし、一部の言語では、文法が言語仕様ではなく L システムとして扱われる場合、生成できない文字列があります。たとえば、^[3]では、文法に S→SS という規則があるとします。生成が 1 つずつ実行される場合、S から始めて、最初に SS を取得し、次に規則を再度適用して SSS を取得できます。ただし、L システムのように、すべての適用可能な規則がすべてのステップで適用される場合は、この文形式を取得できません。代わりに、最初のステップでは SS が得られますが、2 番目のステップではルールを 2 回適用して SSSS が得られます。したがって、特定の文法から L システムによって生成される文字列のセットは、文法によって定義された形式言語のサブセットであり、言語を文字列のセットとして定義すると、特定の L システムは実質的に L システムの文法によって定義された形式言語のサブセットであることを意味します。

各生成規則が個々のシンボルのみを参照し、その隣接シンボルを参照しない場合、L システムは文脈自由です。したがって、文脈自由 L システムは文脈自由文法によって指定されます。規則が単一のシンボルだけでなくその隣接シンボルにも依存する場合、それは文脈依存L システムと呼ばれます。

各シンボルに対して正確に 1 つの生成規則がある場合、L システムは決定論的であると言われます(決定論的コンテキストフリー L システムは一般にD0L システムと呼ばれます)。複数の生成規則があり、各反復中にそれぞれが一定の確率で選択される場合、それは確率論的L システムです。

L システムを使用してグラフィカル イメージを生成するには、モデル内のシンボルがコンピュータ画面上の描画要素を参照する必要があります。たとえば、プログラムFractint は、タートル グラフィックス( Logo プログラミング言語のグラフィックスに類似)を使用して画面イメージを生成します。このプログラムは、L システム モデル内の各定数をタートル コマンドとして解釈します。

藻類の成長をモデル化するための Lindenmayer 独自の L システム。

変数 : AB

定数 : なし

公理  ：A

ルール  : (A → AB)、(B → A)

これにより、次のようになります。

n = 0 : A

n = 1 : AB

n = 2 : ABA

n = 3 : ABAAB

n = 4 : アバアババ

n = 5 : アバアババアバ

n = 6 : アバババババババババ

n = 7 : アバババアバアババアババアババアバ

n=0: 開始（公理/イニシエーター）
                  / \
n=1: AB ルール(A → AB)によって最初の単一のAがABに生成され、ルール(B → A)は適用できませんでした
                /| \
n=2: ABA 元の文字列 AB にすべてのルールが適用され、A が再び AB に生成され、元の B が A に変わります。
             / | | | \
n=3: ABAAB すべての A が最初に自分自身のコピーを生成し、次に B を生成し、それが... になることに注意してください。
           / | | | \ | \ \
n=4: ABAABABA ... 1世代後にAになり、その後生成/繰り返し/再帰を開始します

結果はフィボナッチ語の列です。各文字列の長さを数えると、有名なフィボナッチ数列が得られます(公理の選択により、最初の 1 はスキップされます)。

1 2 3 5 8 13 21 34 55 89 ...

最初の 1 つをスキップしたくない場合は、公理B を使用できます。これにより、 Bノードが上のグラフの 最上位ノード ( A ) の前に配置されます。

各文字列について、文字列の左端からk番目の位置を数えると、黄金比の倍数が間隔 内に収まるかどうかによって値が決定されます。A と B の比率も同様に黄金比に収束します。 ${\displaystyle (k-1,k)}$

この例では、文字列が反転していることを除いて、規則 ( A → AB ) を ( A → BA )に置き換えた場合、同じ結果 ( AとBのシーケンスではなく、各文字列の長さに関して)が生成されます。

このシーケンスは、 （ n世代目）であるため、局所連結シーケンスです。 ${\displaystyle G(n)=G(n-1)G(n-2)}$${\displaystyle G(n)}$

• 変数 : 0, 1
• 定数: "[", "]"
• 公理  : 0
• ルール  : (1 → 11), (0 → 1[0]0)

形状は、生成規則に公理を再帰的に通すことによって構築されます。入力文字列の各文字は、ルール リストに対してチェックされ、出力文字列でどの文字または文字列に置き換えるかが決定されます。この例では、入力文字列の '1' は出力文字列で '11' になりますが、 '[' はそのままです。これを '0' の公理に適用すると、次のようになります。

この文字列は、サイズと複雑さが急速に増大することがわかります。この文字列は、タートル グラフィックスを使用して画像として描画できます。タートル グラフィックスでは、各シンボルにタートルが実行するグ​​ラフィカル操作が割り当てられます。たとえば、上記のサンプルでは、​​タートルに次の指示を与えることができます。

• 0:葉で終わる線分を描く
• 1: 線分を描く
• [: 押す位置と角度、左に45度回転
• ]: ポップの位置と角度、右に45度回転

プッシュとポップはLIFOスタックを指します (より技術的な文法では、「プッシュ位置」と「左折」に別々の記号を使用します)。タートルの解釈が '[' に遭遇すると、現在の位置と角度が保存され、解釈が ']' に遭遇すると復元されます。複数の値が「プッシュ」された場合、「ポップ」は最後に保存された値を復元します。上記のグラフィカル ルールを以前の再帰に適用すると、次のようになります。

変数 : AB

定数 : なし

start  : {開始文字列}

ルール  ：（A → ABA）、（B → BBB）

A は「前進する」を意味し、B は「前進する」を意味します 。

これにより、実直線R上に有名なカントールのフラクタル集合が生成されます。

直角のみを使用する コッホ曲線の変形。

変数 : F

定数 : + −

開始  : F

ルール  : (F → F+F−F−F+F)

ここで、F は「前方に引く」、+ は「左に 90° 回転する」、- は「右に 90° 回転する」を意味します (タートル グラフィックスを参照)。

0の 場合:

ふ

1: 1の 場合

F+F−F−F+F

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

3: 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

L システムを使用して描画された シェルピンスキーの三角形。

変数 : FG

定数 : + −

開始  : F−G−G

ルール  : (F → F−G+F+G−F)、(G → GG)

角度  : 120°

ここで、F と G はどちらも「前進する」を意味し、+ は「角度で左に曲がる」を意味し、- は「角度で右に曲がる」を意味します。

• 
  2 の場合
• 
  4 位
• 
  6件

シェルピンスキーの矢印曲線L システムを 使用して、シェルピンスキーの三角形を近似することも可能です。

変数 : AB

定数 : + −

開始  :A

ルール  : (A → B−A−B)、(B → A+B+A)

角度  : 60°

ここで、A と B は両方とも「前方に引く」ことを意味し、+ は「角度で左に曲がる」ことを意味し、- は「角度で右に曲がる」ことを意味します (タートル グラフィックスを参照)。

L システムを使用して描画された ドラゴンの曲線。

変数 : FG

定数 : + −

開始  : F

ルール  : (F → F+G)、(G → FG)

角度  : 90°

ここで、F と G はどちらも「前進する」を意味し、+ は「角度で左に曲がる」を意味し、- は「角度で右に曲がる」を意味します。

変数 : XF

定数 : + − [ ]

開始  : X

ルール  : (X → F+[[X]-X]-F[-FX]+X)、(F → FF)

角度  : 25°

まず、空のスタックを初期化する必要があります。これは、要素の追加と削除に LIFO (後入れ先出し) 方式に従います。ここで、F は「前方に描画」、- は「右に 25° 回転」、+ は「左に 25° 回転」を意味します。X は描画アクションには対応せず、曲線の展開を制御するために使用されます。角括弧 "[" は、位置と角度の現在の値を保存することに対応するため、位置と角度をスタックの先頭にプッシュし、"]" トークンに遭遇したら、スタックをポップして位置と角度をリセットします。すべての "[" は、すべての "]" トークンの前にあります。

この基本的な L システム技術に関する数多くの詳細が開発されており、それらは相互に組み合わせて使用​​できます。これらの中には、確率文法、文脈依存文法、およびパラメトリック文法があります。

これまで説明してきた文法モデルは決定論的でした。つまり、文法のアルファベット内の任意のシンボルに対して、常に選択される生成規則が 1 つだけ存在し、常に同じ変換を実行します。別の方法としては、シンボルに対して複数の生成規則を指定し、それぞれに発生する確率を与えることです。たとえば、例 2 の文法では、「0」を書き換える規則を次のように変更できます。

0 → 1[0]0

確率的なルールに：

0 (0.5) → 1[0]0

0 (0.5) → 0

この生成では、文字列の書き換え中に「0」に遭遇すると、50% の確率で前述のように動作し、50% の確率で生成中に変化しません。確率的文法を進化的コンテキストで使用する場合、画像の確率的特性が世代間で一定になるように、ランダムシードを遺伝子型に組み込むことをお勧めします。

コンテキスト依存の生成規則は、変更するシンボルだけでなく、その前後に現れる文字列上のシンボルも参照します。たとえば、生成規則は次のようになります。

b < a > c → aa

入力文字列内で「a」が「b」と「c」の間にある場合にのみ、「a」を「aa」に変換します。

…バック…

確率的生成と同様に、異なるコンテキストでシンボルを処理するための複数の生成があります。特定のコンテキストで生成規則が見つからない場合は、同一生成が想定され、変換時にシンボルは変更されません。同じ文法内にコンテキスト依存生成とコンテキストフリー生成の両方が存在する場合、適用可能な場合はコンテキスト依存生成が優先されるものと想定されます。

パラメトリック文法では、アルファベットの各シンボルには、それに関連付けられたパラメータ リストがあります。パラメータ リストと結合されたシンボルはモジュールと呼ばれ、パラメトリック文法の文字列は一連のモジュールです。文字列の例は次のようになります。

a(0,1)[b(0,0)]a(1,2)

パラメータは描画関数でも、生成ルールでも使用できます。生成ルールは、パラメータを 2 つの方法で使用できます。1 つ目は、ルールを適用するかどうかを決定する条件文で、2 つ目は、生成ルールが実際のパラメータを変更する方法です。たとえば、次のようになります。

a(x,y) : x == 0 → a(1, y+1)b(2,3)

モジュール a(x,y) は、条件 x=0 が満たされる場合、この生成規則に従って変換されます。たとえば、a(0,2) は変換されますが、a(1,2) は変換されません。

生成規則の変換部分では、パラメータだけでなくモジュール全体が影響を受ける可能性があります。上記の例では、モジュールb(x,y)が初期パラメータ(2,3)で文字列に追加されます。また、既存のモジュールのパラメータも変換されます。上記の生成規則では、

（0,2）

なる

a(1,3)b(2,3)

a(x,y) の "x" パラメータは明示的に "1" に変換され、a の "y" パラメータは 1 増加します。

パラメトリック文法では、タートルの解釈方法ではなく文法によって線の長さや分岐角度を決定できます。また、モジュールのパラメータとして年齢を指定すると、植物のセグメントの年齢に応じてルールを変更できるため、木のライフサイクル全体のアニメーションを作成できます。

双方向モデルは、記号書き換えシステムを形状の割り当てから明示的に分離します。たとえば、例 2 (フラクタル ツリー) の文字列書き換えプロセスは、記号にグラフィック操作を割り当てる方法に依存しません。言い換えると、特定の書き換えシステムには、無限の数の描画方法を適用できます。

双方向モデルは、1) 順方向プロセスで生成規則を使用して導出ツリーを構築し、2) 逆方向プロセスで段階的に形状を使用してツリーを実現します (葉から根まで)。各逆導出ステップには、基本的な幾何学的位相的推論が含まれます。この双方向フレームワークでは、設計上の制約と目的が文法と形状の変換にエンコードされます。建築設計アプリケーションでは、双方向文法は一貫した内部接続と豊富な空間階層を特徴としています。^[4]

L システムの研究には多くの未解決の問題があります。たとえば、

• 局所的に連鎖するすべての決定論的文脈自由Lシステムの特徴付け。（完全な解は変数が2つだけの場合にのみ知られています）。^[5]
• 構造が与えられた場合、その構造を生成できる L システムを見つけます。^{[引用が必要]}

実数直線 R上の L システム:

• プルーエ・テュー・モース方式

平面R ²上のよく知られた L システムは次のとおりです。

• 空間充填曲線（ヒルベルト曲線、ペアノ曲線、デッキングの教会、コラム）、
• 中位空間充填曲線（レヴィC曲線、ハーター・ハイウェイドラゴン曲線、デイビス・クヌースタードラゴン）、
• タイル張り（スフィンクスタイル張り、ペンローズタイル張り）

• デジタル形態形成
• フラクタル
• 反復関数システム
• ヒルベルト曲線
• 反応拡散システム – 拡散化学試薬シミュレーションを提供する数学モデルの一種（ライフライクを含む）
• 確率的文脈自由文法
• スピードツリー
• 植物のアルゴリズム的美しさ

• Przemysław Prusinkiewicz、Aristid Lindenmayer – The Algorithmic Beauty of Plants PDF版はここから無料で入手できます。Wayback Machineで2021-04-10にアーカイブされました。
• Grzegorz Rozenberg、Arto Salomaa – Lindenmayer Systems: 理論コンピュータサイエンス、コンピュータグラフィックス、および発生生物学への影響 ISBN 978-3-540-55320-5 
• DS Ebert、FK Musgrave、他著 –テクスチャリングとモデリング：手続き型アプローチ、ISBN 0-12-228730-4 
• バリー、ジェーン、バリー・マーク（2010）。『建築の新しい数学』、ニューヨーク：テムズ・アンド・ハドソン。
• Aristid Lindenmayer、「発達における細胞相互作用の数学的モデル」J. Theoret. Biology、18:280—315、1968 年。