L-system

L-systemet eller Lindenmeier-systemet är ett parallellt omskrivningssystem och en typ av formell grammatik . L-systemet består av ett alfabet av tecken som kan användas för att skapa strängar , en uppsättning generativa regler som anger ersättningsregler för varje tecken, en initial sträng (" axiom ") från vilken konstruktionen börjar, och en mekanism för att översätta den genererade strängen till geometriska strukturer. L-systemet föreslogs och utvecklades 1968 av Aristide Lindenmeier , en ungersk biolog och botaniker vid universitetet i Utrecht . Lindenmeier använde L-system för att beskriva beteendet hos växtceller och för att modellera processen för växtutveckling . L-system har också använts för att modellera olika organismers morfologi [1] och kan användas för att generera självliknande fraktaler såsom system med itererade funktioner .

Origins

Som biolog arbetade Lindenmeier med jästsvampar och filamentösa svampar och studerade tillväxtmönster för olika algarter som den blågröna algen Anabaena catenula . Inledningsvis utvecklades L-system för att formellt beskriva utvecklingen av sådana enkla flercelliga organismer och för att illustrera kommunikation mellan närliggande växtceller. Systemet utökades senare för att beskriva högre växter och komplexa förgreningsstrukturer.

L-systemets struktur

Den rekursiva karaktären av reglerna i L-systemet leder till självlikhet , och därför kan fraktalliknande former lätt beskrivas med L-systemet. Växtmodeller och naturligt utseende organiska former är lätta att forma, eftersom modellen långsamt "växer" och blir mer komplex när nivån av rekursion ökar. Lindenmeier-system är också populära i artificiell livsgenerering .

L-systemens grammatik påminner mycket om Thue semi-system (se " Chomskys hierarki "). L-system är nu kända som parametriska L-system, vilka definieras som en tupel

G = ( V , ω, P ),

var

L-systemets grammatikregler tillämpas iterativt, utgående från axiomet (initialtillstånd). Så många regler som möjligt tillämpas per iteration. Det faktum att så många regler som möjligt tillämpas vid varje iteration skiljer L-systemet från ett formellt språk genererat från en formell grammatik som bara tillämpar en regel per iteration. Om slutledningsreglerna tillämpades en i taget skulle det vara lätt att skapa ett språk snarare än ett L-system. L-system är alltså en delmängd av språk.

Ett L-system är kontextfritt om varje slutledningsregel endast hänvisar till enskilda tecken och inte till deras grannar. Kontextfria L-system definieras av en kontextfri grammatik . Om regeln inte bara beror på en enskild symbol, utan även på närliggande symboler, kallas systemet ett kontextkänsligt L-system.

Om det finns exakt en regel för varje symbol sägs L-systemet vara deterministiskt (ett deterministiskt kontextoberoende L-system kallas ett D0L-system ). Om det finns flera regler, och var och en väljs med viss sannolikhet vid varje iteration, så är detta ett stokastiskt L-system.

För att använda L-system för att generera grafiska bilder krävs att symbolerna i modellen hänvisar till bildens element på datorskärmen. Till exempel använder programmet Fractint sköldpaddsgrafik (liknande grafik i logospråket ) för att skapa en bild på skärmen. Programmet tolkar varje konstant i L-systemmodellen som kommandon för sköldpaddsgrafiksystem.

Exempel på L-system

Exempel 1: Alger

Lindenmeiers ursprungliga L-system för modellering av algtillväxt.

variabler  : AB konstanter  : nej axiom  : A regler  : (A → AB), (B → A)

Systemet ger

n = 0 : A n = 1: AB n = 2: ABA n = 3: ABAAB n = 4: ABAABABA n = 5: ABAABABAABAAB n = 6: ABAABABAABAABABAABABABA n = 7: ABAABABAABAABABAABABAABAABABAABAAB Exempel 1: Alger, förklaring n=0: En start (axiom/initiator) / \ n=1: AB initial singel A blir AB av regel (A → AB), regel (B → A) kan inte tillämpas /| \ n=2: ABA alla regler gäller för sträng AB, A blir AB igen och B blir A /| | |\ n=3: ABAAB notera att alla A:n översätts till en kopia av sig själva och B läggs till, vilket blir ... /| | |\ |\ \ n=4: ABAABABA ... till A i nästa generation, vilket resulterar i rekursion

Resultatet blir Fibonacci-ord . Om vi ​​räknar längden på varje rad får vi den berömda Fibonacci-sekvensen (som utelämnar den första 1):

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

För varje rad, om vi räknar den k: te positionen från den vänstra änden av raden, beror värdet på om k gånger det gyllene snittet faller inom intervallet . Förhållandet mellan förekomsterna av bokstäverna A till B konvergerar också till det gyllene snittet.

Detta exempel ger samma resultat (i termer av stränglängd, inte i termer av sekvensen av bokstäverna A och B ) om regeln ( A → AB ) ersätts med ( A → BA ), men vi får spegelvända strängar.

Denna sekvens är catenant av eftersom , där är den n :e generationen.

Exempel 2: Pythagoras träd

  • variabler : 0, 1
  • konstanter : [, ]
  • axiom : 0
  • regler : (1 → 11), (0 → 1[0]0)

Figuren är konstruerad genom att rekursivt tillämpa inferensreglerna på axiomet. Varje tecken i inmatningssträngen kontrolleras mot listan med regler för att bestämma vad tecknet ska ersättas med. I det här exemplet blir "1" på ingången "11" på utgången, men "[" ändras inte. Genom att tillämpa slutledningsreglerna på axiomet "0" får vi:

axiom: 0
1:a rekursionen: 1[0]0
2:a rekursionen: 11[1[0]0]1[0]0
3:e rekursionen: 1111[11[1[0]0]1[0]0]11[1[0]0]1[0]0
…

Vi ser strängar växa snabbt i längd och komplexitet. En sträng kan ritas som en bild med hjälp av sköldpaddsgrafik , där varje karaktär har en motsvarande grafikoperation för en sköldpadda. I det här exemplet kan följande kommandon ges till sköldpaddan:

  • 0: rita ett segment som slutar på ett blad
  • 1: dra en linje
  • [: stack draw position och vinkel, rotera vänster 45 grader
  • ]: avläs position och vinkel från stapeln, rotera åt höger 45 grader

"Push on the stack" och "pop off the stack" syftar på LIFO-stacken (mer detaljerad grammatik skulle kräva att delas upp i "lägg på stapeln" och "rotera"). När tolken stöter på "[", lagras sköldpaddans aktuella position och rörelsevinkel på stapeln; när "]" påträffas återställs positionen och vinkeln. Om flera värden skjuts upp i stacken, återställs det senast skjutna värdet. I litteraturen kallas L-system som använder detta tillvägagångssätt för förgrening "bracketed L-systems" (bracketed L-systems) [2] .

Genom att tillämpa dessa grafiska regler på den tidigare erhållna strängen har vi:

  • Axiom

  • Första rekursionen

  • Andra rekursionen

  • Tredje rekursionen

  • Fjärde rekursionen

  • Sjunde rekursion, reducerad tiofaldig

Exempel 3: Cantor set

variabler : AB konstanter : nej start : En {startsträng} regler : (A → ABA), (B → BBB)

Låt A betyda "dra en linje" och B betyda "flytta".

En sådan grammatik genererar den berömda Cantor-fraktaluppsättningen på den verkliga axeln R .

Exempel 4: Koch Curve

Variant av Koch-kurvan , med endast räta vinklar.

variabler  : F konstanter  : + − start  : F regler  : (F → F+F−F−F+F)

Här betyder F "dra en linje", + betyder "rotera 90° åt vänster" och − betyder "rotera 90° åt höger" (se " Sköldpaddsgrafik ").

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

Exempel 5: Sierpinski-triangeln

Sierpinski triangel , ritad med L-systemet.

variabler : FG konstanter : + − start : F−G−G regel : (F → F−G+F+G−F), (G → GG) vinkel : 120°

Här betyder F och G "dra en linje", + betyder "sväng höger vid ett hörn", och − betyder "sväng vänster vid ett hörn".

  • n=2

  • n=4

  • n=6

Du kan också uppskatta Sierpinski-triangeln med hjälp av Sierpinskis pil-kurva L-system .

variabler : AB konstanter : + − start : A regler : (A → B−A−B), (B → A+B+A) vinkel : 60°

Här betyder A och B "dra en linje", + betyder "sväng vänster i en vinkel" och − betyder "sväng höger i en vinkel" (se " Sköldpaddsgrafik ").

Iterationer för n =2, n =4, n =6, n =8

Exempel 6: Dragon Curve

Dragon Curve , ritad med L-systemet.

variabler  : XY konstanter  : F + − start  : FX regler  : (X → X+YF+), (Y → −FX−Y) vinkel  : 90°

Här betyder F "dra en linje", − betyder "rotera 90° åt vänster", och + betyder "rotera 90° åt höger". X och Y motsvarar inte någon rithandling, utan används endast för att rita en kurva.


Iterationer för n = 10, n = 15

Exempel 7: Fraktalväxt

variabler  : XF konstanter  : + − [ ] start  : X regler  : (X → F−[[X]+X]+F[+FX]−X), (F → FF) vinkel  : 25°

Här betyder F "dra en linje", − betyder "rotera 25° åt vänster" och + betyder "rotera 25° åt höger". X motsvarar inte någon rithandling, det används endast för att rita en kurva. Den hakparentes "[" motsvarar att spara aktuella positions- och vinkelvärden, som återställs när motsvarande "]"-tecken exekveras.

Fraktalväxt för n = 6

Alternativ

Flera utvecklingar har gjorts baserade på L-systemtekniken som kan användas i kombination. Bland dem finns stokastiska grammatiker , sammanhangskänsliga grammatiker och parametriska grammatiker.

Stokastiska grammatiker

De grammatikmodeller vi just har övervägt är deterministiska. Det vill säga, givet valfritt tecken från alfabetet finns det exakt en regel som alltid väljs och samma substitution utförs alltid. Ett alternativ är att specificera mer än en slutledningsregel för en karaktär, vilket ger varje regel en sannolikhet för exekvering. Till exempel, i grammatiken i exempel 2 kan vi ersätta omskrivningsregeln "0" med

0 → 1[0]0

på sannolikhetsregeln

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

Med dessa slutledningsregler, när en "0" påträffas i inmatningssträngen, finns det en 50% chans att beteendet blir detsamma som tidigare, och en 50% chans att ingenting kommer att förändras. Om en stokastisk grammatik används i evolutionens sammanhang , rekommenderas det att generatorn av slumpmässighet införlivas i genotypen , så att de stokastiska egenskaperna hos mönstret förblir konstanta mellan generationerna.

Kontextkänsliga grammatiker

En kontextkänslig slutledningsregel tittar inte bara på tecknen den ändrar, utan också på tecknen som föregår och följer dem. Till exempel slutledningsregeln:

b < a > c → aa

konverterar "a" till "aa", men bara om "a" råkar vara mellan "b" och "c" i inmatningssträngen:

…tillbaka…

Precis som med slumpmässig slutledning finns det flera regler för att hantera karaktärer i olika sammanhang. Om ingen genereringsregel hittas för det angivna sammanhanget antas en identitetsomvandling och symbolen ändras inte. Om det finns både kontextoberoende och beroende slutledningsregler i samma grammatik, har den kontextkänsliga inferensregeln företräde (om den kan tillämpas).

Parametriska grammatiker

I en parametrisk grammatik har varje tecken i alfabetet en parameterlista kopplad till tecknet. En symbol tillsammans med parametrar kallas en modul, och en sträng i en parametrisk grammatik är en sekvens av moduler. Ett exempel skulle vara följande rad:

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

Parametrar kan användas av både ritningsfunktionen och slutledningsreglerna. Inferensregler kan använda parametrar på två sätt. I det första fallet används parametern i ett villkorligt uttryck som avgör om slutledningsregeln ska tillämpas. I det andra fallet kan slutledningsregeln ersätta de faktiska parametrarna. Till exempel slutledningsregeln:

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

Modulen a(x,y) genomgår en transformation enligt denna regel om x=0 gäller. Till exempel kommer a(0,2) att genomgå en transformation, men a(1,2) inte.

På höger sida av slutledningsregeln (i efterföljaren) kan både parametrar och hela moduler transformeras. I exemplet ovan läggs modulen b(x,y) till strängen med initiala parametrar (2,3). Parametrarna för en redan befintlig modul konverteras. Med reglerna som beskrivs ovan,

a(0,2)

Blir

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

eftersom parametern "x" för modulen a(x,y) explicit omvandlas till "1", och parametern "y" ökas med en.

Parametriska grammatiker tillåter att längden på segmentet och grenens vinkel specificeras i grammatiken och inte i metoderna för att tolka sköldpaddsgrafik. Om åldern också är inställd som en parameter för modulen kan reglerna ändras beroende på växtsegmentets ålder, vilket gör att du kan skapa en animering av trädets hela livscykel.

Andra kategorier av L-system

  • D0L-system = deterministiska kontextfria system (se ovan)
  • Propagativa L-system ("Propagativa L-system", "pL-system") är system där minst en regel har minst två bokstäver på höger sida (i utdata). Icke-avelsystem har bara en symbol på höger sida. Ordets längd i detta fall ändras inte [3] .
  • L-system med fäste (se exempel 2)
  • 0L-system, 1L-system, 2L-system (IL-system, även kända som (k,l)-system) [4] .
  • Tabellformiga L-system ("T0L-system") är system som arbetar med flera uppsättningar av regler. En extern kontrollmekanism används för att välja en uppsättning regler. Tabellformade L-system introducerades och formaliserades av Rosenberg 1975 för att modellera miljöns påverkan på växttillväxt [5] .

Öppna nummer

Det finns många öppna problem förknippade med studiet av L-system. Till exempel:

  • Beskrivning av alla deterministiska kontextfria lokalt katentiva L-system. (Den fullständiga lösningen är endast känd för tre variabler) [6] .
  • Givet en struktur, hitta ett L-system som kan reproducera denna struktur.
  • Givet två pL-system och en interpolationsfunktion, kommer de resulterande ritningarna att vara kongruenta [4] ?
  • Givet ett pL-system och en tolkningsfunktion, kommer den resulterande kurvan att stängas? Kommer det att vara självkorsande eller trädliknande? Kommer vissa linjeavsnitt att ritas mer än en gång? [4] ?

Svaren på dessa frågor är intressanta inte bara ur en teoretisk synvinkel, de är också användbara för att bygga pL-system för att skapa ritningar med givna egenskaper [4] .

Typer av L-system

L-system på den reella axeln R :

Välkända L-system på planet R 2 :

Se även

Anteckningar

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

Litteratur

  • Grzegorz Rozenberg, Arto Salomaa. Den matematiska teorin för L-system. - New York: Academic Press, 1980. - ISBN 0-12-597140-0 .
  • Przemysław Prusinkiewicz, Aristid Lindenmayer . Den algoritmiska skönheten hos växter. — Springer, 2004.
  • Grzegorz Rozenberg, Arto Salomaa. Lindenmayer Systems: Inverkan på teoretisk datavetenskap, datorgrafik och utvecklingsbiologi. - Springer-Verlag, 1992. - ISBN 978-3-540-55320-5 .
  • D.S. Ebert, F.K. Musgrave, D. Peachey, K. Perlin. Texturering och modellering: en processuell metod. - Academic Press, 1994. - ISBN 0-12-228730-4 .
  • Burry, Jane, Burry Mark. Arkitekturens nya matematik. — New York: Thames och Hudson, 2010.
  • Aristid Lindenmayer. Matematiska modeller för cellulär interaktion i utveckling // J. Theoret. Biologi. - 1968. - Utgåva. 18 . - S. 280-315 .
  • P. prusinkiewicz. Proceedings of Graphics Interface '86 / Vision Interface '86. - 1986. - S. 247−253 ..
  • Handbook of Formal Languages ​​/ G.Rozenberg, A.Salomaa. - Springer, 1997. - V. 1 (Ord, språk, grammatik). - S. 253-328. - ISBN 978-3-642-63863-3 .
  • Stelios Manousakis. Musikaliska L-system. - Haag: Kungliga konservatoriet, 2006. - (Masteruppsats - Sonologi).

Länkar