L-rendszer

Az elméleti számítógép-tudomány , egy L-rendszer vagy Lindenmayer rendszer egy formális újraírása vagy nyelvtani rendszer , feltalálta 1968-ban a magyar biológus Aristid Lindenmayer . Az L-rendszer modellezi a növények vagy baktériumok fejlődésének és szaporodásának folyamatát .

Ez a generatív nyelvtan egyik formája. Ezeket a nyelvtanokat számos szerző grafikusan implementálta, ami látványos képeket eredményezett. Egy bizonyos készítmény szisztematikus tanulmányozását Przemysław Prusinkiewicz (en) végezte el az 1980-as években. Matematikai tanulmány, amely azonnal elkezdődött, amint Lindenmayer bevezette a rendszereket, egy kidolgozott elmélethez vezetett, amelynek első szintézise már 1980-ban megtörtént. , Rozenberg és Salomaa.

Kezdetben Lindenmayer formalizálását a formális nyelvek modelljeként fogja fel, amely lehetővé teszi az egyszerű többsejtű organizmusok fejlődésének leírását. Ebben az időben élesztőkön , gombákon és algákon dolgozott . De a számítástechnika elméletei és gyakorlói hatására ez a rendszer hivatalos nyelvcsaládokhoz vezetett, és olyan módszerekhez is vezetett, amelyek grafikusan generálják az igen összetett idealizált növényeket.

Formálisan az L-rendszer olyan szabályok és szimbólumok összessége, amelyek az élőlények, például a növények vagy a sejtek növekedési folyamatát modellezik. Az L-rendszerek központi fogalma az átírás fogalma . Az átírás az összetett objektumok felépítésének technikája egy egyszerű kezdeti objektum egyes részeinek átírási szabályok használatával.

Biológiai értelmezésben a sejteket szimbólumok segítségével modellezik. Minden generációval a sejtek osztódnak, amelyet egy szimbólum egy vagy több egymást követő szimbólumra cserélésének művelete modellez.

Rendszer átírása

Az L-rendszer egy átírási rendszer, amely a következőket tartalmazza:

Ábécé : az L-rendszer változóinak halmaza. Jelöljük a „szimbólumokkal” felépíthető „szavak” halmazát és a legalább egy szimbólumot tartalmazó szavak halmazát; $V$ $V ^ {*}$ $V$ $V ^ {+}$
Állandó értékek halmaza . E szimbólumok egy része minden L-rendszerben közös (lásd a Turtle alábbi értelmezését ); $S$
A kiindulási axióma az , látható, mint a kezdeti állapot; $w$ $V ^ {+}$
A szimbólumok átírási, megjegyzett reprodukciós szabályainak halmaza . $P$ $V$

L-rendszert jegyeznek fel . A formális nyelvtannal való különbség a szabályok alkalmazásában rejlik: egy L-rendszerben minden lépésnél az összes változó helyettesítve van, míg egy nyelvtanban csak egy változó cserélődik ki. ${\ displaystyle \ {V, S, w, P \}}$

Példa és jelölések egyszerű L-rendszerekre

Itt van a "Lindenmayer alga", Aristid Lindenmayer L-rendszere, amelyet az algák fejlődésének leírására használtak:

Ábécé: V = {A, B}
Állandók: S = {}
Kiinduló axióma: w = A
Szabályok: (A → AB), (B → A)

Rövidített jelölés: Algue { Axiom A ; A=AB, B=A}

A hasonló egyenletet úgy A=ABkell érteni, hogy az A bármelyik szimbólum AB "szó" lesz a következő generációban.

Íme az eredmény hat generáción keresztül:

n = 0, A
n = 1, AB
n = 2, AB A
n = 3, AB A AB
n = 4, AB A AB AB A
n = 5, AB A AB AB A AB A AB
n = 6, AB A AB AB A AB A AB AB A AB AB A

Ha minden egyes iterációnál megszámoljuk a szimbólumok számát, akkor megkapjuk a Fibonacci szekvenciát , az első két tag kivételével .

Teknős értelmezése

A kapott karakterlánc grafikusan értelmezhető, két vagy három dimenzióban. Két dimenzióban azt képzeljük, hogy egy kéz egy ceruzát tart, amely az utasítások szerint mozog a lapon: "menjen fel egy rovattal, majd forduljon 20 ° -kal balra, mozogjon kétszer egy fokkal, jegyezze meg a helyzetét, és lépjen tovább egy lépéssel, kelj fel, majd pihenj a memorizált pozíción ”és így tovább ... Ezért bevezetjük a guide V vagy állandó ∈ S variáns szimbólumokat a kéz irányításához. Közülük többen szabványosítottak, részei annak, amit angolul " Turtle interpretációnak " neveznek . Ez a név a Logo programozási nyelv "teknőséből" származik, amely ugyanazon az elven működik. Valójában ez a teknős az a kéz, amelyik a ceruzát tartja. A leggyakrabban használt jelek:

F: Mozgás egyetlen lépéssel (∈ V);
+: Forduljon balra α (∈ S) szöggel;
-: Forduljon jobbra α (∈ S) szögben;
&: Forduljon lefelé egy α szöggel (∈ S);
^: Forgasson felfelé egy α (∈ S) szöggel;
<: Hajtson balra α (∈ S) szögben;
>: Hajtson jobbra α (∈ S) szögben;
| : Kapcsolja be magát 180 ° -kal (∈ S);
[: Az aktuális pozíció mentése (∈ S);
]: Az utoljára mentett pozíció (∈ S) visszaállítása.

Pontosabban: az V-hez tartozó szimbólumok egy növény részei, például egy ág vagy csak egy ág egy része. Az S-hez tartozó szimbólumok olyan rendek, amelyeket a növényt megrajzoló virtuális kezünknek adunk, ezek segítségével meghatározzuk az irányt, míg a V szimbólumok ebben az irányban rajzolnak.

Megjegyzés: az utolsó két szimbólum felidézi az OpenGl pushMatrix () és popMatrix () függvényeit , így sejthetjük, hogy ez egy grafikus környezet, amely nagyon jól alkalmazza magát az L-rendszernek. Ezenkívül a mutatókkal történő objektum-orientált programozás, például a C ++ nyelvben , jelennek tűnik a fejlődő "sejtlánc" modellezéséhez.

Példa a Koch-görbére

Változó: v = {F}
Állandók: S = {+, -}
Axióma: w = F
Szabály: (F → F + F - F - F + F)

Courbe_de_Koch
{
angle 90
axiom F
F=F+F−F−F+F
}

angle 90meghatározza, hogy 90 ° -ot fordulunk a + és - szimbólumokkal.

Íme az eredmény három generáción keresztül:

n = 0:

n = 1:

F + FF-F + F

n = 2:

F + FF-F + F + F + FF-F + F - F + FF-F + F - F + FF-F + F + F + FF-F + F

n = 3:

F + FF-F + F + F + FF-F + F-F + FF-F + F-F + FF-F + F + F + FF-F + F + F + FF-F + F + F + FF-F + F-F + FF-F + F-F + FF-F + F + F + FF-F + F - F + FF-F + F + F + FF-F + F-F + FF-F + F-F + FF-F + F + F + FF-F + F - F + FF-F + F + F + FF-F + F-F + FF-F + F-F + FF-F + F + F + FF-F + F + F + FF-F + F + F + FF-F + F-F + FF-F + F-F + FF-F + F + F + FF-F + F

Háromdimenziós teknős

Ezt a "teknősértelmezést" három dimenzióban lehet kiaknázni Harold Abeson és Andrea diSessa ötleteinek köszönhetően a "Teknős geometria: a számítógép mint a matematika feltárásának közegében" közös munkájuknak. A teknőshöz kapcsolódó három vektor lehetővé teszi a következő tájolásváltozás megadását:

${\ vec H}$ , , Ilyen például a (vektor termék) ${\ vec L}$ ${\ vec U}$ ${\ vec H} \ szor {\ vec L} = {\ vec U}$

${\ vec H}$ teknős irányába. Ez a teknős kinézete.
${\ vec U}$ legfeljebb. A teknős "teteje". Ez az az irány, amely a teknősből a hátsó részéből (vagyis a héja kidudorodó oldaláról) jön ki.
${\ vec L}$ balra. Ez a teknős bal oldala.

Ezután a teknős forgását megjegyezzük:

${\ displaystyle [{\ vec {H}} '{\ vec {L}}' {\ vec {U}} '] = [{\ vec {H}} {\ vec {L}} {\ vec {U }}] R}$ ahol R jelentése 3 × 3 mátrix .

Az α szög elfordulása a tengelyek körül , vagy a mátrixok képviselik őket: ${\ vec U}$ ${\ vec L}$ ${\ vec H}$

$RU (\ alpha) = {\ kezdete {pmatrix} \ cos (\ alfa) & \ sin (\ alfa) & 0 \\ - \ sin (\ alfa) & \ cos (\ alfa) & 0 \\ 0 & 0 & 1 \ end {pmatrix}}$

$RL (\ alpha) = {\ kezdődik {pmatrix} cos (\ alpha) & 0 & - \ sin (\ alpha) \\ 0 & 1 & 0 \\\ sin (\ alfa) & 0 & \ cos (\ alfa) \ end {pmatrix}}$

$RH (\ alfa) = {\ kezdődik {pmatrix} 1 & 0 & 0 \\ 0 & \ cos (\ alfa) & - \ sin (\ alfa) \\ 0 & \ sin (\ alfa) & \ cos (\ alfa) \ end {pmatrix}}$

A szimbólumok most a következő jelentést kapják:

+: forduljon balra egy α szöggel, a tengely körül , azaz használja az RU (α) forgásmátrixot; ${\ vec U}$
-: forduljon jobbra egy α szöggel, a tengely körül , azaz használja az RU (−α) forgásmátrixot; ${\ vec U}$
&: forgasson lefelé egy α szöggel, a tengely körül , azaz használja az RL (α) forgásmátrixot; ${\ vec L}$
∧: forgasson felfelé egy α szöggel, a tengely körül , azaz használja az RL (−α) forgásmátrixot; ${\ vec L}$
/: váltás jobbra egy α szöggel, a tengely körül , azaz az RH (α) forgásmátrix segítségével; ${\ vec H}$
\: balra döntsön egy α szöggel, a tengely körül , azaz használja az RH (−α) forgásmátrixot; ${\ vec H}$
| : forduljon maga körül 180 ° -kal , azaz forduljon meg az RU (180◦) forgatómátrix segítségével.

DOL-rendszer vagy Determinisztikus 0-kontextusú rendszer

A "D" rövidítés a "determinisztikus" és a "0" a "kontextustól független" rövidítéseket használja a rendszer egy adott kategóriájának kijelölésére. Egy rendszer akkor determinista, ha minden generációban csak egy lehetséges evolúciót kínál az axiómából. Egy ok következményt generál, amelynek eredményeként: egy változó csak egyfajta átalakításon megy keresztül, mindig azonos, ezért változónként csak egy szabály. Ez a fejlődés ráadásul független a kontextustól. Az első példa egy D0L-rendszer, ez az L-rendszer legegyszerűbb formája.

Példa egy D0L-rendszerre

Változó: V = {F, X}
Állandók: S = {+, -, [,]}
Axióma: w = X
Szabályok: (X → F [+ X] F [−X] + X) ^ (F → FF)

Szimbolikus jelölés: Plante { angle 20 axiom X ; X=F[+X]F[−X]+X; F=FF }

angle 20határozza meg, melyik szöget fordítsa a + és - szimbólumokkal. Íme két generáció eredménye:

n = 0, X
n = 1, F [+ X] F [-X] + X
n = 2, FF [+ F [+ X] F [−X] + X] FF [−F [+ X] F [−X] + X] + F [+ X] F [−X] + X

Egy ilyen rendszer valószínűségeket használ. A D0L-rendszertől eltérően a szimbólum többféle átalakítása között is lehet választani. Minden választást egy bizonyos valószínűség súlyoz.

Példa az S0L-rendszerre

Változó: V = {F, X}
Állandók: S = {+, -, [,]}
Axióma: w = X
Szabályok: X → F [++ X] F [−X] + X; X → F [+ X] F [-X] + X; F → FF

Az X → F [++ X] F [−X] + X és X → F [+ X] F [−X] + X szabályokat 0,2, illetve 0,8 valószínűséggel alkalmazzuk.

Itt van egy lehetséges eredmény két generáción keresztül:

n = 0, X
n = 1, F [++ X] F [−X] + X
n = 2, FF [++ F [+ X] F [−X] + X] FF [−F [+ X] F [−X] + X] + F [+ X] F [−X] + X

Itt van egy másik lehetséges eredmény két generáció során:

n = 0, X
n = 1, F [+ X] F [-X] + X
n = 2, F [+ F [++ X] F [−X] + X] F [−F [++ X] F [−X] + X] + F [++ X] F [−X] + X

Két generáció alatt 2² = 4 lehetséges lehetőség áll rendelkezésre, különböző valószínűségekkel.

Környezetérzékeny rendszerek

A két előző rendszer (0L-rendszerek) nem tudja szimulálni a növény egyes részeinek kölcsönhatásának hatását, mert ezek nem kontextuálisak ( angolul : kontextus-mentesek ), azaz mindegyik rész a többi résztől függetlenül fejlődik. Az L-rendszerű környezetérzékeny (angolul " context-sensitive " ) figyelembe veszi azt, ami megelőzi vagy követi a helyettesítendő szimbólumot. Az ilyen rendszert IL-rendszernek vagy másképpen ( k , l ) rendszernek is nevezik , amikor a bal oldali kontextus egy k hosszúságú szó, a jobb oldalon pedig egy l hosszúságú szó . Amikor a kontextus kedvező, a helyettesítést a szabály szerint hajtják végre, különben nincs helyettesítés. Íme két példa:

1. példa: akropetális jel

Ez az L-rendszer egy akropetális jel terjedését szimulálja olyan ágágakban, amelyek nem fejlődnek ki.

Változó: V = {A, B}
Állandók: S = {+, -, [,]}
Axióma: w = B [+ A] A [−A] A [+ A] A
Szabályok: (B <A → B)

A szabály <szimbólumát a következőképpen értelmezzük: ha az A szimbólumot megelőzi egy B szimbólum, akkor ez az A B-vel válik a következő generációban, különben változatlan marad. Ebben az értékelésben az állandókat figyelmen kívül hagyják.

Itt van a jel terjedése három generáción keresztül; a + és - jeleket figyelmen kívül hagyják a szabályok figyelembevételével:

n = 0, B [+ A] A [−A] A [+ A] A
n = 1, B [+ B] B [−A] A [+ A] A
n = 2, B [+ B] B [−B] B [+ A] A
n = 3, B [+ B] B [−B] B [+ B] B

Látjuk, hogy az egyes ágakat fokozatosan éri el az akropetális jel, amely lehetővé teszi a legmagasabb virágok kinyílását. Minden generációban két új elágazás fogadja a jelet, valójában, mivel mentjük a pozíciót, felhívjuk az A-t, majd visszaállítjuk a pozíciót és újrarajzolunk egy A-t, ez azt jelenti, hogy ennek a két A-nak ugyanaz az alapja, tehát ugyanaz az elágazás előzi meg mindkettőt.

2. példa: bazipetális jel

Ez az L-rendszer szimulálja a basipete jel terjedését olyan ágágakban, amelyek nem fejlődnek ki.

Változó: V = {A, B}
Állandók: S = {+, -, [,]}
Axióma: w = A [+ A] A [−A] A [+ A] B
Szabályok: (A> B → B)

A olyan ág, amely még nem kapta meg a jelet, és B olyan ág, amely megkapta. A szabályt a következőképpen értjük: ha az A szimbólumot B szimbólum követi, akkor ez az A B-vel válik a következő generációban.

Itt van a jel terjedése három generáción keresztül, tudva, hogy a + és - jeleket figyelmen kívül hagyják a szabályok figyelembevételével:

n = 0, A [+ A] A [−A] A [+ A] B
n = 1, A [+ A] A [−A] B [+ B] B
n = 2, A [+ A] B [−B] B [+ B] B
n = 3, B [+ B] B [−B] B [+ B] B

Látható, hogy az egyes ágakat fokozatosan éri el a basipete jel, amely lehetővé teszi, hogy a virágzatú virágok esernyőben vagy fejben centrifugális módon virágozzanak.

A (B <A <B → B) forma szabályának lehetséges megírása azt jelenti, hogy ha az A elágazást B elágazások veszik körül, akkor a következő generációban B elágazattá válik. Több szabály megírása is lehetséges, több helyzetre is.

Függelékek

Megjegyzések és hivatkozások

Rozenberg és Salomaa 1980 .

Bibliográfia

Könyvek

Grzegorz Rozenberg és Arto Salomaa , Az L-rendszerek matematikai elmélete , Academic Press ,1980
(en) Przemyslaw Prusinkiewicz és Aristid Lindenmayer , „A növények algoritmikus szépsége” , 1990
Grzegorz Rozenberg és Arto Salomaa , The Book of L , Springer-Verlag , 2012 (1986 első kiadásának újranyomása), 492 p. ( ISBN 978-3-642-95488-7 )
en) Przemyslaw Prusinkiewicz és James Hanan, Lindenmayer Systems, fraktálok és növények ,1992

Cikkek

Karel Klouda és Štěpán Starosta , „ Körkörös D0L-rendszerek jellemzése ”, Elméleti informatika , 1. évf . 790,2019, P. 131–137 ( DOI 10.1016 / j.tcs.2019.04.021 ).

Galéria és szoftver

Charlie Chernohorsky, Fractal Galéria , 2004.
(en) Az L-rendszerek grafikus és zenei értelmezése . (Java alkalmazás)
LOGO és L-rendszerek

Külső linkek

(en) A biológiai modellezés és vizualizáció kutatócsoport publikációi
(en) Tanszék ökoinformatikai, biometriai és erdőnövekedési tanszéke a göttingeni Georg-August Egyetemen Növekedési nyelvtanok

Lásd is