L-rendszer

Az L-rendszer vagy a Lindenmeier-rendszer egy párhuzamos újraíró rendszer és a formális nyelvtan egy típusa . Az L-rendszer karakterláncok létrehozására használható karakterek ábécéjéből áll , generatív szabályokból , amelyek minden karakterhez helyettesítési szabályokat adnak meg, egy kezdeti karakterláncból (" axiómából "), amelyből az építés kezdődik, és egy mechanizmusból. a generált karakterlánc geometriai struktúrákká való lefordításához. Az L-rendszert 1968-ban Aristide Lindenmeier , az Utrechti Egyetem magyar biológusa és botanikusa javasolta és fejlesztette ki . Lindenmeier L-rendszereket használt a növényi sejtek viselkedésének leírására és a növények fejlődési folyamatának modellezésére . Az L-rendszereket különféle organizmusok morfológiájának modellezésére is használták [1] , és önhasonló fraktálok , például iterált függvényrendszerek létrehozására .

Eredet

Lindenmeier biológusként élesztőgombákkal és fonalas gombákkal dolgozott, és különféle algafajok, például az Anabaena catenula kék-zöld alga növekedési mintázatait tanulmányozta . Kezdetben L-rendszereket fejlesztettek ki az ilyen egyszerű többsejtű szervezetek fejlődésének formális leírására és a szomszédos növényi sejtek közötti kommunikáció szemléltetésére. A rendszert később kiterjesztették magasabb rendű növények és összetett elágazó struktúrák leírására.

Az L-rendszer felépítése

Az L-rendszer szabályainak rekurzív jellege önhasonlósághoz vezet , ezért a fraktálszerű formák könnyen leírhatók az L-rendszer segítségével. A növénymodellek és a természetesnek tűnő szerves formák könnyen kialakíthatók, mivel a modell lassan "növekszik", és a rekurzió szintjének növekedésével összetettebbé válik. A Lindenmeier rendszerek a mesterséges életgenerálásban is népszerűek .

Az L-rendszerek nyelvtana nagyon hasonlít a Thue félrendszerekhez (lásd " Chomsky hierarchiája "). Az L-rendszereket manapság parametrikus L-rendszereknek nevezik, amelyeket leíróként határoznak meg

G = ( V , ω, P ),

ahol

Az L-rendszer nyelvtani szabályait iteratív módon alkalmazzuk, az axiómából (kezdeti állapotból) kiindulva. A lehető legtöbb szabályt alkalmazzuk iterációnként. Az a tény, hogy minden iterációnál a lehető legtöbb szabályt alkalmazzák, elválasztja az L-rendszert a formális nyelvtanból generált formális nyelvtől, amely iterációnként csak egy szabályt alkalmaz. Ha a következtetési szabályokat egyenként alkalmaznák, egyszerűbb lenne nyelvet generálni, nem pedig L-rendszert. Így az L-rendszerek a nyelvek egy részhalmaza.

Egy L-rendszer környezetfüggetlen, ha minden következtetési szabály csak az egyes karakterekre vonatkozik, a szomszédaikra nem. A kontextusmentes L-rendszereket egy kontextusmentes nyelvtan határozza meg . Ha a szabály nem csak egyetlen szimbólumtól függ, hanem a szomszédos szimbólumoktól is, akkor a rendszert környezetérzékeny L-rendszernek nevezzük.

Ha minden szimbólumra pontosan egy szabály vonatkozik, akkor az L-rendszert determinisztikusnak mondjuk (a determinisztikus környezetfüggetlen L-rendszert D0L rendszernek nevezzük ). Ha több szabály van, és mindegyiket bizonyos valószínűséggel választjuk ki minden iterációnál, akkor ez egy sztochasztikus L-rendszer.

Ahhoz, hogy az L-rendszereket grafikus képek előállítására használhassuk, a modellben szereplő szimbólumoknak a számítógép képernyőjén megjelenő kép elemeire kell utalniuk. Például a Fractint program teknős grafikát használ (hasonlóan a Logo nyelv grafikájához ), hogy képet állítson elő a képernyőn. A program az L-rendszermodell minden konstansát teknős grafikus rendszerparancsként értelmezi.

Példák L-rendszerekre

1. példa: Alga

A Lindenmeier eredeti L-rendszere az algák növekedésének modellezésére.

változók  : AB állandók  : nem axióma  : A szabályok  : (A → AB), (B → A)

A rendszer ad

n = 0: A n = 1: AB n = 2: ABA n = 3: ABAAB n = 4: ABAABABA n = 5: ABAABABAABAAB n = 6 : ABAABABAABAABABAABABABA n = 7 : ABAABABAABAABABAABABAABAABABAABAAB 1. példa: Algák, magyarázat n=0: Kezdés (axióma/kezdeményező) / \ n=1: AB kezdő egyszeri A szabály alapján AB lesz, a (B → A) szabály nem alkalmazható /| \ n=2: ABA minden szabály vonatkozik az AB karakterláncra, A ismét AB lesz, B pedig A /| | |\ n=3: Az ABAAB vegye figyelembe, hogy az összes A-t saját maguk másolatává fordítják, és hozzáadják B-t, amiből ... /| | |\ |\ \ n=4: ABAABABA ... A-ba a következő generációban, ami rekurziót eredményez

Az eredmény Fibonacci szavak lesznek . Ha megszámoljuk az egyes sorok hosszát, akkor a híres Fibonacci sorozatot kapjuk (az első 1 kihagyásával):

1 2 3 5 8 13 21 34 55 89 ...

Ha minden sornál a k- adik pozíciót számoljuk a sor bal végétől, akkor az érték attól függ, hogy az aranymetszés k - szerese beleesik- e az intervallumba . Az A-B betűk előfordulási aránya is az aranymetszéshez konvergál.

Ez a példa ugyanazt az eredményt adja (a karakterlánc hosszát tekintve, nem az A és B betűk sorrendjét tekintve), ha az ( A → AB ) szabályt ( A → BA ) helyettesítjük, de tükrözött karakterláncokat kapunk.

Ez a szekvencia az katenője, mivel , ahol az n- edik generáció.

2. példa: A Pitagorasz-fa

  • változók : 0, 1
  • állandók : [, ]
  • axióma : 0
  • szabályok : (1 → 11), (0 → 1[0]0)

Az ábra a következtetési szabályok axiómára való rekurzív alkalmazásával készül. A bemeneti karakterlánc minden egyes karakterét összevetjük a szabályok listájával, hogy meghatározzuk, mire kell lecserélni a karaktert. Ebben a példában az "1" a bemeneten "11" lesz a kimeneten, de a "[" nem változik. A következtetési szabályokat a "0" axiómára alkalmazva a következőket kapjuk:

alapigazság: 0
1. rekurzió: 1[0]0
2. rekurzió: 11[1[0]0]1[0]0
3. rekurzió: 1111[11[1[0]0]1[0]0]11[1[0]0]1[0]0
…

Azt látjuk, hogy a húrok hossza és összetettsége gyorsan nő. Egy karakterlánc képként rajzolható teknős grafikával , ahol minden karakternek megvan a megfelelő grafikus művelete a teknőshöz. Ebben a példában a következő parancsok adhatók a teknősnek:

  • 0: levélben végződő szakasz rajzolása
  • 1: húzz egy vonalat
  • [: veremhúzási pozíció és szög, elforgatás balra 45 fokkal
  • ]: pozíció és szög leolvasása veremből, forgatás jobbra 45 fokkal

A "Push on the stack" és a "pop off the stack" a LIFO veremre utal (a részletesebb nyelvtanhoz a "rakás a verembe" és a "forgatás" részekre kell bontani). Amikor a tolmács a „[” jellel találkozik, a teknős jelenlegi helyzete és mozgási szöge a veremben tárolódik; ha „]” találkozik, a helyzet és a szög visszaáll. Ha több érték kerül a verembe, akkor az utoljára tolt érték áll vissza. A szakirodalomban az elágazás ilyen megközelítését alkalmazó L-rendszereket "zárójeles L-rendszereknek" (bracketed L-systems) nevezik [2] .

Ha ezeket a grafikus szabályokat alkalmazzuk a korábban kapott karakterláncra, a következőt kapjuk:

  • Alapigazság

  • Első rekurzió

  • Második rekurzió

  • Harmadik rekurzió

  • Negyedik rekurzió

  • Hetedik rekurzió, tízszeresére csökkentve

3. példa: Cantor készlet

változók : AB állandók : nem start : A {start string} szabályok : (A → ABA), (B → BBB)

Legyen A jelentése „vonalat húz”, B pedig „mozgást”.

Egy ilyen nyelvtan generálja a híres Cantor-fraktálkészletet az R valós tengelyen .

4. példa: Koch-görbe

A Koch-görbe változata , csak derékszögeket használva.

változók  : F állandók  : + − kezdés  : F szabályok  : (F → F+F−F−F+F)

Itt az F jelentése "vonalat húz", a + azt jelenti, hogy "90°-kal balra forog", a − pedig azt, hogy "90°-kal jobbra forog" (lásd: " Teknős grafika ").

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

5. példa: Sierpinski-háromszög

Sierpinski-háromszög , L-rendszerrel rajzolva.

változók : FG állandók : + − kezdés : F−G−G szabály : (F → F−G+F+G−F), (G → GG) szög : 120°

Itt F és G azt jelenti, hogy „vonalat húz”, a + azt jelenti, hogy „saroknál jobbra forduljon”, a - pedig „saroknál balra forduljon”.

  • n=2

  • n=4

  • n=6

A Sierpinski- háromszöget a Sierpinski nyílgörbe L-rendszerrel is közelítheti .

változók : AB állandók : + − kezdés : A szabályok : (A → B−A−B), (B → A+B+A) szög : 60°

Itt A és B azt jelenti, hogy "vonalat húz", a + azt jelenti, hogy "szöggel balra fordul" és a − azt jelenti, hogy "forduljon jobbra egy szöggel" (lásd a " Teknős grafikát ").

Iterációk n =2, n =4, n =6, n =8 esetén

6. példa: Dragon Curve

Sárkánygörbe , L-rendszerrel rajzolva.

változók  : XY állandók  : F + − kezdés  : FX szabályok  : (X → X+YF+), (Y → −FX−Y) szög  : 90°

Itt az F jelentése „vonal rajzolása”, − jelentése „balra 90°-kal forgatás”, a + pedig „90°-kal jobbra forgatás”. X és Y nem felel meg semmilyen rajzolási műveletnek, hanem csak görbe rajzolására használják.


Iterációk n = 10, n = 15 esetén

7. példa: Fraktál növény

változók  : XF állandók  : + − [ ] kezdés  : X szabályok  : (X → F−[[X]+X]+F[+FX]−X), (F → FF) szög  : 25°

Itt az F jelentése "vonalat húz", - azt jelenti, hogy "25°-kal balra forog", a + pedig azt, hogy "25°-kal jobbra forog". X nem felel meg semmilyen rajzolási műveletnek, csak görbe rajzolására szolgál. A "[" szögletes zárójel az aktuális pozíció és szögértékek mentését jelenti, amelyek a megfelelő "]" karakter végrehajtásakor visszaállnak.

Fraktál növény n = 6 esetén

Opciók

Az L-system technikára alapozva számos fejlesztés történt, amelyek együtt használhatók. Ezek közé tartoznak a sztochasztikus nyelvtanok , a környezetérzékeny nyelvtanok és a parametrikus nyelvtanok.

Sztochasztikus nyelvtanok

Az imént vizsgált nyelvtani modellek determinisztikusak. Vagyis az ábécé bármely karakterét figyelembe véve pontosan egy szabály van, amelyet mindig kiválasztanak, és mindig ugyanazt a helyettesítést hajtják végre. Alternatív megoldásként egynél több következtetési szabályt ad meg egy karakterhez, így mindegyik szabály végrehajtásának valószínűségét adja meg. Például a 2. példa nyelvtanában a „0” átírási szabályt lecserélhetjük erre

0 → 1[0]0

a valószínűségi szabályon

0 (0,5) → 1[0]0 0 (0,5) → 0

Ezekkel a következtetési szabályokkal, ha a bemeneti karakterláncban "0" található, 50% esély van arra, hogy a viselkedés ugyanaz lesz, mint korábban, és 50% az esélye annak, hogy semmi sem fog változni. Ha sztochasztikus nyelvtant használunk az evolúció kontextusában , akkor ajánlott a véletlenszerűség generátorát beépíteni a genotípusba , hogy a minta sztochasztikus tulajdonságai generációk között állandóak maradjanak.

Környezetérzékeny nyelvtanok

A környezetérzékeny következtetési szabály nem csak az általa módosított karaktereket veszi figyelembe, hanem az őket megelőző és követő karaktereket is. Például a következtetési szabály:

b < a > c → aa

átalakítja az "a"-t "aa"-ra, de csak akkor, ha az "a" "b" és "c" között van a bemeneti karakterláncban:

…bac…

A véletlenszerű következtetésekhez hasonlóan számos szabály létezik a karakterek kezelésére különböző kontextusokban. Ha nem található generálási szabály a megadott kontextushoz, akkor a rendszer identitásátalakítást feltételez, és a szimbólum nem változik. Ha ugyanabban a nyelvtanban vannak kontextusfüggetlen és függő következtetési szabályok is, akkor a kontextusérzékeny következtetési szabály élvez elsőbbséget (ha alkalmazható).

Paraméteres nyelvtanok

A parametrikus nyelvtanban az ábécé minden karakteréhez tartozik egy paraméterlista a karakterhez. A szimbólumot a paraméterekkel együtt modulnak nevezzük, a karakterláncot pedig a parametrikus nyelvtanban modulok sorozatának nevezzük. Példa erre a következő sor:

a(0,1)[b(0,0)]a(1,2)

A paramétereket a rajzoló függvény és a következtetési szabályok egyaránt használhatják. A következtetési szabályok kétféleképpen használhatják a paramétereket. Az első esetben a paramétert egy feltételes kifejezésben használják, amely meghatározza, hogy a következtetési szabályt alkalmazni kell-e. A második esetben a következtetési szabály helyettesítheti a tényleges paramétereket. Például a következtetési szabály:

a(x,y) : x == 0 → a(1, y+1)b(2,3)

Az a(x,y) modul e szabály szerint átalakul, ha x=0 teljesül. Például a(0,2) átalakul, de a(1,2) nem.

A következtetési szabály jobb oldalán (az utódban) mind a paraméterek, mind a teljes modulok átalakíthatók. A fenti példában a b(x,y) modul hozzáadódik a kezdeti paraméterekkel (2,3) rendelkező karakterlánchoz. Egy már létező modul paraméterei konvertálódnak. A fent leírt szabályok szerint

a(0,2)

válik

a(1,3)b(2,3)

mivel az a(x,y) modul "x" paramétere kifejezetten "1"-re van konvertálva, az "y" paraméter pedig eggyel nő.

A paraméteres nyelvtanok lehetővé teszik, hogy a szegmens hosszát és az elágazás szögét a nyelvtanban adják meg, és nem a teknősgrafika értelmezési módszereiben. Ha az életkor is be van állítva a modul paramétereként, akkor a szabályok a növényszegmens életkorától függően módosíthatók, ami lehetővé teszi a fa teljes életciklusának animációját.

Az L-rendszerek egyéb kategóriái

  • D0L rendszerek = determinisztikus környezetfüggetlen rendszerek (lásd fent)
  • A szaporító L-rendszerek ("Propagative L-systems", "pL-systems") olyan rendszerek, amelyekben legalább egy szabálynak legalább két betűje van a jobb oldalon (a kimenetben). A nem tenyésztési rendszereknek csak egy szimbóluma van a jobb oldalon. A szó hossza ebben az esetben nem változik [3] .
  • Konzolos L-rendszerek (lásd a 2. példát)
  • 0L-rendszerek, 1L-rendszerek, 2L-rendszerek (IL-rendszerek, más néven (k,l)-rendszerek) [4] .
  • A táblázatos L-rendszerek ("T0L-rendszerek") olyan rendszerek, amelyek több szabálykészlettel működnek. Egy külső vezérlőmechanizmust használnak a szabálykészlet kiválasztására. A táblázatos L-rendszereket Rosenberg vezette be és formalizálta 1975-ben, hogy modellezzék a környezetnek a növények növekedésére gyakorolt ​​hatását [5] .

Nyitott kérdések

Számos nyitott probléma van az L-rendszerek tanulmányozásával kapcsolatban. Például:

  • Az összes determinisztikus kontextusmentes lokális katentív L-rendszer leírása. (A teljes megoldás csak három változó esetén ismert) [6] .
  • Adott egy struktúra, keressen egy L-rendszert, amely képes reprodukálni ezt a struktúrát.
  • Adott két pL-rendszer és egy interpolációs függvény, az eredményül kapott rajzok kongruensek lesznek [4] ?
  • Adott egy pL rendszer és egy interpretációs függvény, az eredményül kapott görbe zárva lesz? Önmetsző vagy faszerű lesz? Egyes vonalszakaszokat többször is megrajzolnak? [4] ?

Az ezekre a kérdésekre adott válaszok nem csak elméleti szempontból érdekesek, hanem pL-rendszerek felépítésében is hasznosak adott tulajdonságú rajzok létrehozásához [4] .

L-rendszerek típusai

L-rendszerek az R valós tengelyen :

Jól ismert L-rendszerek az R 2 síkon :

Lásd még

Jegyzetek

  1. ↑ Rozenberg, Salomaa, 1980 .
  2. ↑ Manousakis, 2006 , p. 26.
  3. ↑ Manousakis, 2006 , p. 28.
  4. ↑ 1 2 3 4 Prusinkiewicz, 1986 , p. 252.
  5. ↑ Manousakis, 2006 , p. 29.
  6. ↑ Kari, Rozenberg, Salomaa, 1997 , p. 262.

Irodalom

  • Grzegorz Rozenberg, Arto Salomaa. Az L rendszerek matematikai elmélete. - New York: Academic Press, 1980. - ISBN 0-12-597140-0 .
  • Przemysław Prusinkiewicz, Aristid Lindenmayer . A növények algoritmikus szépsége. — Springer, 2004.
  • Grzegorz Rozenberg, Arto Salomaa. Lindenmayer Systems: Hatás az elméleti számítástechnikára, a számítógépes grafikára és a fejlődésbiológiára. - Springer-Verlag, 1992. - ISBN 978-3-540-55320-5 .
  • D. S. Ebert, F. K. Musgrave, D. Peachey, K. Perlin. Textúra és modellezés: eljárási megközelítés. - Academic Press, 1994. - ISBN 0-12-228730-4 .
  • Burry, Jane, Burry Mark. Az építészet új matematikája. – New York: Temze és Hudson, 2010.
  • Aristid Lindenmayer. Matematikai modellek a sejtes interakcióhoz a fejlődésben // J. Theoret. Biológia. - 1968. - Kiadás. 18 . - S. 280-315 .
  • P. prusinkiewicz. Proceedings of Graphics Interface '86 / Vision Interface '86. - 1986. - S. 247-253 ..
  • Formális nyelvek kézikönyve / G.Rozenberg, A.Salomaa. - Springer, 1997. - V. 1 (Szó, Nyelv, Nyelvtan). - S. 253-328. - ISBN 978-3-642-63863-3 .
  • Stelios Manousakis. Musical L-Systems. - Hága: A Királyi Konzervatórium, 2006. - (Mastertézis - Szonológia).

Linkek