L-Systemの強さ

複数 multipuleの書き換え rewriting ルールを同時parallel (対語 sequentially 順次) 行う 、というL-systemの規則が強烈。同時に書き換えるということは、生物学上の振る舞いを想定したものであった。

alphabet: { a }, start word: { aaa }, ruleA: { a -> aa }.

  • sequentially rewriting  順次書き換え の場合

aaa –ruleA–> aaaa
aaaa –ruleA–> aaaaa
とすべての長さの aaaaa….. を表現できる

  • parallel 平行書き換えの場合

aaa –ruleA–> aaaaaa
aaaaaa –ruleA–> aaaaaaaaaaaa
とすべての長さの aaaaa….. を表現しにくように見えるが

ruleB: { a -> a }.を加え平行書き換えしながら複数書き換えを行うと

aaa -> (a->a) (a->a) (a->aa) == aaaa
とすべての長さの aaaaa….. を表現できる。つまりL-systemはChomskyチョムスキー階層にはうまく当てはまらない、ということになる

 

Comments are closed.