L-system
直角で構成されるコッホ曲線の描画例。
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 でシェルピンスキーの三角形を作図する例。
V : A, B
S : +, -
ω: A
P : (A → B−A−B), (B → A+B+A)
上記において、A 及び B はタートルによる直線の描画、+ はタートルを左へ60°回転、同じく- は右へ60°回転する事を意味する。同様の図形を描く置換規則は他にもあるが、この規則の場合、タートルは三角形の左下から描き始める事になる。
L-system の基本は再帰性で、自己相似図形やフラクタル図形のような形状を簡単に記述する事ができる。植物やその他の見た目が自然な生物構造も同様に簡単に定義でき、再帰呼出の回数を増やす事であたかも構造が「成長」し、複雑化していくように見える。L-system は人工生命の生成にもよく用いられる。
L-system の文法は en:Unrestricted grammar のものに似ている(→ チョムスキー階層)。現在では、以下のような四ツ組によって定義されることが多い。
G = {V, S, ω, P},
各要素は、
V(文字): 置換規則(後述の P )により順次置き換えられてゆく変数の集合。L-system の再帰的な反復計算が進んでいく時に、物として「成長」してゆくのはこの V の要素からなる文字列である。
S : 計算が進んでも変化しない定数の集合。
ω : システムの初期状態を示すV の要素からなる文字列。
P : V を変化させてゆく置換規則の集合。各要素は、例えば (A → AB) のように、置換前(置換対象)の文字列と置換後の文字列の組み合わせにより記述される。