L-systemをやってみる

L-systemとは

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

wikipedliaの引用だが、要は自己相似図形、フラクタル図形作成に利用でき、植物の成長モデルなど、自然の構造を記述できるアルゴリズムだ。また、構造は以下の通り

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

各要素は、

• V（文字）： 置換規則（後述の P ）により順次置き換えられてゆく変数の集合。L-system の再帰的な反復計算が進んでいく時に、物として「成長」してゆくのはこの V の要素からなる文字列である。
• S ： 計算が進んでも変化しない定数の集合。
• ω ： システムの初期状態を示すV の要素からなる文字列。
• P ： V を変化させてゆく置換規則の集合。各要素は、例えば (A → AB) のように、置換前（置換対象）の文字列と置換後の文字列の組み合わせにより記述される。

簡単にまとめると

pythonで実装

pythonで以下の例で実装してみる。

コードは以下の通り

omega = "A"
P = {"A":"A+B","B":"B+B--A"}
repeat = 3

result = omega
for i in range(repeat):
    result = result.translate(str.maketrans(P))
    print(result)

結果は以下の通り

A+B
A+B+B+B--A
A+B+B+B--A+B+B--A+B+B--A--A+B