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 の文法は 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, BS ： なしω ： AP ： (A → AB), (B → A)順次計算してゆくと、文字列は以下のように成長する。
n = 0 ： An = 1 ： ABn = 2 ： ABAn = 3 ： ABAABn = 4 ： ABAABABAこの例では、置換規則 P において、(A → AB) は不均等な細胞分裂 により通常の細胞Aと未熟な細胞Bが生じる事を表し、(B → A) は未熟な細胞Bが成長して分裂可能な細胞 A へと成熟する事を表している。この文字列を図形化（例えば A を分枝 型の細胞、B を小型の細胞の図などにそれぞれ置き換える）する事で、あたかも寒天培地 上に展開した藻類のコロニー のような絵を得る事ができる。
V ： A, BS ： なしω ： AP ： (A → B), (B → AB)計算を進めると、以下のような文字列となる。
n = 0 ： An = 1 ： Bn = 2 ： ABn = 3 ： BABn = 4 ： ABBABn = 5 ： BABABBABn = 6 ： ABBABBABABBABn = 7 ： BABABBABABBABBABABBABこの文字列の各文字数を n =0 から順に数えると、フィボナッチ数列 （1 1 2 3 5 8 13 21 34 55 89 …）となっている。この例では文字列の内容は問わず長さだけに注目しているので、例えば置換規則の (B → AB) を (B → BA) で置き換えても同様の数列を得る事ができる。
V ： A, BS ： なしω ： AP ： (A → ABA), (B → BBB)計算を進めると、以下のような文字列となる。
n = 0 ： An = 1 ： ABAn = 2 ： ABABBBABAn = 3 ： ABABBBABABBBBBBBBBABABBBABAこの文字列の A を線分、B を抜き取られた部分に置き換えると下のような図が得られる。置換規則の (A → ABA) は線分 （閉区間 ）を3等分して中央を抜き取る操作に相当する。(B → BBB) は一度取り除かれた区間が戻らない事を意味する。詳しくはカントール集合 （Cantor set ）を参照
直角で構成されるコッホ曲線 の描画例。
V ： FS ： +, -;ω ： FP ： (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, BS ： +, -ω ： AP ： (A → B−A−B), (B → A+B+A)上記において、A 及び B はタートルによる直線の描画、+ はタートルを左へ60°回転、同じく- は右へ60°回転する事を意味する。同様の図形を描く置換規則は他にもあるが、この規則の場合、タートルは三角形の左下から描き始める事になる。
n = 2, n = 4, n = 6, n = 8 の時にそれぞれ描画される図形。n → ∞ の時、シェルピンスキーの三角形に等しくなる。
通常のコッホ曲線 に、周期的な角度の変更を加えながら描画したフラクタル図形の一種。
L-system に関する問題は数多く存在するが、その最たるものは L-system を逆に辿る事が困難であるというものである。具体的には、ある構造が示された時に、その構造を生成するパラメータや置換規則を見つける事が難しい。これは自然物のような複雑な（反復回数の多い）過程を経て形成された図形に顕著である。
実数 列における L-system：
平面 における L-system：
空間 における L-system：
確率的 (Stochastic) L-systemは、L-systemを拡張して確率的に分岐できるようにしたものである。確率的L-systemには標準が無いため、ソフトウェアによって文法が異なる。
以下は確率的な分岐を行うL-systemの実装毎の例である。
Tong Linの実装
Houdini
Cinema 4D
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の実装などが存在する。
.jpg)
.jpg)
.jpg)
