L-System - formallang.memo

"Mathematical Models for Cellular Interactions in Development I and II" (1968)

L-Systemを提案した論文。生物の細胞分裂による成長のようなもののモデル化として提案された。形式言語理論そのもの以外にも、ＣＧにおけるフラクタル形状の生成などに広く応用されている。名前は著者名 Lindenmayer の頭文字 "L" から（Dalen1970 http://dx.doi.org/10.1007/BF01702868）。

• Aristid Lindenmayer
• Journal of Theoretical Biology, vol. 18 pp. 300-315
• http://dx.doi.org/10.1016/0022-5193(68)90079-9
• http://dx.doi.org/10.1016/0022-5193(68)90080-5

iL-System (i-sided L-System)

Ｇ＝<Σ,ω,δ>

• Σ： alphabet
• ω： axiom. 開始文字列（∈Σ*）
• δ： a1..ai → α の形の導出規則の集まり（ただしδはcomplete: すべてのa1..aiに対して1個は対応するαがある）

1ステップの書き換え規則は

• a1a2...an => α1α2...αn if and only if
  • a1..ai -> α1 ∈ δ
  • a2..ai+1 -> α2 ∈ δ
  • ...

で定義される。L(G) = {t∈Σ* | ω=>*t}。i-sided だとi文字だけ後ろのコンテキストを見ながら変換がかかる感じ。

オリジナル論文では、特に 1L と 2L が考察されている。0L-System は特に別途更に考察されている。言ってみれば 1L, 2L, .. は context-sensitive なシステムで、0L は context-free なシステム。

---