L-system

L-systemet eller Lindenmeier-systemet er et parallelt omskrivningssystem og en form for formel grammatik . L-systemet består af et alfabet af tegn, der kan bruges til at skabe strenge , et sæt generative regler , der specificerer erstatningsregler for hvert tegn, en indledende streng (" aksiom "), hvorfra konstruktionen starter, og en mekanisme til oversættelse af den genererede streng til geometriske strukturer. L-systemet blev foreslået og udviklet i 1968 af Aristide Lindenmeier , en ungarsk biolog og botaniker ved Universitetet i Utrecht . Lindenmeier brugte L-systemer til at beskrive plantecellers adfærd og modellere processen med planteudvikling . L-systemer er også blevet brugt til at modellere morfologien af ​​forskellige organismer [1] og kan bruges til at generere selv-lignende fraktaler såsom systemer med itererede funktioner .

Oprindelse

Som biolog arbejdede Lindenmeier med gær og trådsvampe og studerede vækstmønstrene for forskellige algearter såsom blågrønalgen Anabaena catenula . Oprindeligt blev L-systemer udviklet til formelt at beskrive udviklingen af ​​sådanne simple flercellede organismer og for at illustrere kommunikation mellem naboplanteceller. Systemet blev senere udvidet til at beskrive højere planter og komplekse forgreningsstrukturer.

Struktur af L-systemet

Den rekursive karakter af reglerne i L-systemet fører til selv-lighed , og derfor kan fraktallignende former let beskrives ved hjælp af L-systemet. Plantemodeller og naturligt udseende organiske former er nemme at forme, da modellen langsomt "vokser" og bliver mere kompleks, efterhånden som niveauet af rekursion øges. Lindenmeier-systemer er også populære i kunstig livsgenerering .

L-systemernes grammatikker minder meget om Thue semi-systemerne (se " Chomskys hierarki "). L-systemer er nu kendt som parametriske L-systemer, som er defineret som en tupel

G = ( V , ω, P ),

hvor

L-systemets grammatikregler anvendes iterativt, startende fra aksiomet (indledende tilstand). Så mange regler som muligt anvendes pr. iteration. Det faktum, at der anvendes så mange regler som muligt ved hver iteration, adskiller L-systemet fra et formelt sprog genereret fra en formel grammatik , der kun anvender én regel pr. iteration. Hvis slutningsreglerne blev anvendt en ad gangen, ville det være let at generere et sprog frem for et L-system. L-systemer er således en delmængde af sprog.

Et L-system er kontekstfrit, hvis hver inferensregel kun refererer til individuelle karakterer og ikke til deres naboer. Kontekstfrie L-systemer er defineret af en kontekstfri grammatik . Hvis reglen ikke kun afhænger af et enkelt symbol, men også af nabosymboler, kaldes systemet et kontekstfølsomt L-system.

Hvis der er præcis én regel for hvert symbol, siges L-systemet at være deterministisk (et deterministisk kontekstuafhængigt L-system kaldes et D0L-system ). Hvis der er flere regler, og hver enkelt er valgt med en vis sandsynlighed ved hver iteration, så er dette et stokastisk L-system.

For at bruge L-systemer til generering af grafiske billeder kræves det, at symbolerne i modellen refererer til billedets elementer på computerskærmen. For eksempel bruger programmet Fractint skildpaddegrafik (svarende til grafik i logosproget ) til at producere et billede på skærmen. Programmet fortolker hver konstant i L-systemmodellen som kommandoer til skildpaddegrafiksystem.

Eksempler på L-systemer

Eksempel 1: Alger

Lindenmeiers originale L-system til modellering af algevækst.

variable  : AB konstanter  : nej aksiom  : A regler  : (A → AB), (B → A)

Systemet giver

n = 0 : A n = 1: AB n = 2: ABA n = 3: ABAAB n = 4: ABAABABA n = 5: ABAABABAABAAB n = 6: ABAABABAABAABABAABABABA n = 7: ABAABABAABAABABAABABAABAABABAABAAB Eksempel 1: Alger, forklaring n=0: En start (aksiom/initiator) / \ n=1: AB indledende enkelt A bliver AB ved regel (A → AB), regel (B → A) kan ikke anvendes /| \ n=2: ABA gælder alle regler for streng AB, A bliver AB igen, og B bliver til A /| | |\ n=3: ABAAB bemærk, at alle A'er er oversat til en kopi af dem selv, og B tilføjes, hvilket bliver ... /| | |\ |\ \ n=4: ABAABABA ... til A i næste generation, hvilket resulterer i rekursion

Resultatet bliver Fibonacci-ord . Hvis vi tæller længden af ​​hver linje, får vi den berømte Fibonacci-sekvens (udeladt den første 1):

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

For hver række, hvis vi tæller den k'te position fra venstre ende af rækken, afhænger værdien af, om k gange det gyldne snit falder inden for intervallet . Forholdet mellem forekomsterne af bogstaverne A til B konvergerer også til det gyldne snit.

Dette eksempel giver det samme resultat (med hensyn til strenglængde, ikke i forhold til rækkefølgen af ​​bogstaver A og B ), hvis reglen ( A → AB ) erstattes af ( A → BA ), men vi får spejlede strenge.

Denne sekvens er catenant af siden , hvor er den n . generation.

Eksempel 2: Det pythagoræiske træ

  • variable : 0, 1
  • konstanter : [, ]
  • aksiom : 0
  • regler : (1 → 11), (0 → 1[0]0)

Figuren er konstrueret ved rekursivt at anvende slutningsreglerne på aksiomet. Hvert tegn i inputstrengen kontrolleres i forhold til listen over regler for at bestemme, hvad tegnet skal erstattes med. I dette eksempel bliver "1" på input til "11" på output, men "[" ændres ikke. Ved at anvende slutningsreglerne på aksiomet "0", får vi:

aksiom: 0
1. rekursion: 1[0]0
2. rekursion: 11[1[0]0]1[0]0
3. rekursion: 1111[11[1[0]0]1[0]0]11[1[0]0]1[0]0
…

Vi ser strenge vokse hurtigt i længde og kompleksitet. En streng kan tegnes som et billede ved hjælp af skildpaddegrafik , hvor hver karakter har en tilsvarende grafikoperation for en skildpadde. I dette eksempel kunne følgende kommandoer gives til skildpadden:

  • 0: tegn et segment, der ender på et blad
  • 1: Tegn en streg
  • [: stak trækposition og vinkel, drej 45 grader til venstre
  • ]: aflæs position og vinkel fra stakken, drej 45 grader til højre

"Skub på stakken" og "spring ud af stakken" refererer til LIFO-stakken (mere detaljeret grammatik ville kræve opdeling i "sæt på stakken" og "roter"). Når tolken støder på "[", gemmes skildpaddens aktuelle position og bevægelsesvinkel på stakken; når "]" stødes på, gendannes positionen og vinklen. Hvis flere værdier skubbes ind på stakken, gendannes den sidst skubbede værdi. I litteraturen kaldes L-systemer, der anvender denne tilgang til forgrening, "Bracketed L-systemer" (Bracketed L-systemer) [2] .

Ved at anvende disse grafiske regler på den tidligere opnåede streng har vi:

  • Aksiom

  • Første rekursion

  • Anden rekursion

  • Tredje rekursion

  • Fjerde rekursion

  • Syvende rekursion, reduceret tidoblet

Eksempel 3: Cantor sæt

variable : AB konstanter : nej start : En {startstreng} regler : (A → ABA), (B → BBB)

Lad A betyde "træk en streg" og B betyder "bevæge sig".

En sådan grammatik genererer det berømte Cantor-fraktalsæt på den reelle akse R.

Eksempel 4: Koch Curve

Variant af Koch-kurven , der kun bruger rette vinkler.

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

Her betyder F "tegn en linje", + betyder "drej til venstre 90°", og − betyder "drej 90° til højre" (se " Skildpaddegrafik ").

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

Eksempel 5: Sierpinski-trekanten

Sierpinski trekant , tegnet med L-systemet.

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

Her betyder F og G "træk en linje", + betyder "drej til højre ved et hjørne", og − betyder "drej til venstre ved et hjørne".

  • n=2

  • n=4

  • n=6

Du kan også tilnærme Sierpinski trekanten ved hjælp af Sierpinski pil-kurve L-system .

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

Her betyder A og B "tegn en linje", + betyder "drej til venstre i en vinkel", og − betyder "drej til højre i en vinkel" (se " Skildpaddegrafik ").

Iterationer for n =2, n =4, n =6, n =8

Eksempel 6: Dragon Curve

Dragon Curve , tegnet med L-systemet.

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

Her betyder F "tegn en linje", − betyder "drej 90° til venstre", og + betyder "drej 90° til højre". X og Y svarer ikke til nogen tegnehandling, men bruges kun til at tegne en kurve.


Iterationer for n = 10, n = 15

Eksempel 7: Fraktalplante

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

Her betyder F "tegn en linje", − betyder "drej 25° til venstre", og + betyder "drej 25° til højre". X svarer ikke til nogen tegnehandling, det bruges kun til at tegne en kurve. Den firkantede parentes "[" svarer til at gemme de aktuelle positions- og vinkelværdier, som gendannes, når det tilsvarende "]"-tegn udføres.

Fraktal plante for n = 6

Indstillinger

Der er lavet flere udviklinger baseret på L-system teknikken, der kan bruges sammen. Blandt dem er stokastiske grammatikker , kontekstfølsomme grammatikker og parametriske grammatikker.

Stokastiske grammatikker

De grammatikmodeller, vi lige har overvejet, er deterministiske. Det vil sige, givet et hvilket som helst tegn fra alfabetet, er der nøjagtig én regel, der altid vælges, og den samme substitution udføres altid. Et alternativ er at specificere mere end én inferensregel for et tegn, hvilket giver hver regel en sandsynlighed for udførelse. For eksempel, i grammatikken i eksempel 2, kan vi erstatte omskrivningsreglen "0" med

0 → 1[0]0

på sandsynlighedsreglen

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

Med disse slutningsregler, når et "0" stødes på i inputstrengen, er der en 50% chance for, at adfærden vil være den samme som før, og en 50% chance for, at intet ændrer sig. Hvis en stokastisk grammatik bruges i sammenhæng med evolution , anbefales det, at generatoren af ​​tilfældighed inkorporeres i genotypen , så de stokastiske egenskaber af mønsteret forbliver konstante mellem generationerne.

Kontekstfølsomme grammatikker

En kontekstafhængig inferensregel ser ikke kun på de tegn, den ændrer, men også på de tegn, der går forud for og efter dem. For eksempel inferensreglen:

b < a > c → aa

konverterer "a" til "aa", men kun hvis "a" tilfældigvis er mellem "b" og "c" i inputstrengen:

…tilbage…

Som med tilfældig inferens er der flere regler for håndtering af tegn i forskellige sammenhænge. Hvis der ikke findes en genereringsregel for den angivne kontekst, antages en identitetstransformation, og symbolet ændres ikke. Hvis der er både kontekstuafhængige og afhængige slutningsregler i samme grammatik, har den kontekstfølsomme slutningsregel forrang (hvis den kan anvendes).

Parametriske grammatikker

I en parametrisk grammatik har hvert tegn i alfabetet en parameterliste knyttet til tegnet. Et symbol sammen med parametre kaldes et modul, og en streng i en parametrisk grammatik er en sekvens af moduler. Et eksempel kunne være følgende linje:

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

Parametre kan bruges af både tegnefunktionen og slutningsreglerne. Inferensregler kan bruge parametre på to måder. I det første tilfælde bruges parameteren i et betinget udtryk, der bestemmer, om inferensreglen skal anvendes. I det andet tilfælde kan inferensreglen erstatte de faktiske parametre. For eksempel inferensreglen:

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

Modulet a(x,y) gennemgår en transformation efter denne regel, hvis x=0 gælder. For eksempel vil a(0,2) gennemgå en transformation, men a(1,2) vil ikke.

På højre side af inferensreglen (i efterfølgeren) kan både parametre og hele moduler transformeres. I eksemplet ovenfor tilføjes modulet b(x,y) til strengen med startparametre (2,3). Parametrene for et allerede eksisterende modul konverteres. Med reglerne beskrevet ovenfor,

a(0,2)

Bliver til

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

da parameteren "x" i modulet a(x,y) eksplicit konverteres til "1", og parameteren "y" øges med én.

Parametriske grammatikker gør det muligt at specificere længden af ​​segmentet og grenens vinkel i grammatikken og ikke i metoderne til fortolkning af skildpaddegrafik. Hvis alderen også er sat som parameter for modulet, kan reglerne ændres afhængigt af plantesegmentets alder, hvilket giver mulighed for at lave en animation af hele træets livscyklus.

Andre kategorier af L-systemer

  • D0L-systemer = deterministiske kontekstfrie systemer (se ovenfor)
  • Propagative L-systemer ("Propagative L-systemer", "pL-systemer") er systemer, hvor mindst én regel har mindst to bogstaver på højre side (i output). Ikke-avlssystemer har kun ét symbol på højre side. Ordets længde i dette tilfælde ændres ikke [3] .
  • L-systemer med beslag (se eksempel 2)
  • 0L-systemer, 1L-systemer, 2L-systemer (IL-systemer, også kendt som (k,l)-systemer) [4] .
  • Tabular L-systemer ("T0L-systemer") er systemer, der arbejder med flere sæt regler. En ekstern kontrolmekanisme bruges til at vælge et sæt regler. Tabellformede L-systemer blev introduceret og formaliseret af Rosenberg i 1975 for at modellere miljøets indflydelse på plantevækst [5] .

Åbne numre

Der er mange åbne problemer forbundet med studiet af L-systemer. For eksempel:

  • Beskrivelse af alle deterministiske kontekstfrie lokalt katentive L-systemer. (Den komplette løsning kendes kun for tre variabler) [6] .
  • Givet en struktur, find et L-system, der kan gengive denne struktur.
  • Givet to pL-systemer og en interpolationsfunktion, vil de resulterende tegninger være kongruente [4] ?
  • Givet et pL-system og en fortolkningsfunktion, vil den resulterende kurve blive lukket? Vil det være selvskærende eller træ-lignende? Vil nogle linjestykker blive tegnet mere end én gang? [4] ?

Svarene på disse spørgsmål er interessante, ikke kun fra et teoretisk synspunkt, de er også nyttige til at bygge pL-systemer til at lave tegninger med givne egenskaber [4] .

Typer af L-systemer

L-systemer på den reelle akse R :

Velkendte L-systemer på planet R 2 :

Se også

Noter

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

Litteratur

  • Grzegorz Rozenberg, Arto Salomaa. Den matematiske teori om L-systemer. - New York: Academic Press, 1980. - ISBN 0-12-597140-0 .
  • Przemysław Prusinkiewicz, Aristid Lindenmayer . Planternes algoritmiske skønhed. - Springer, 2004.
  • Grzegorz Rozenberg, Arto Salomaa. Lindenmayer Systems: Indvirkning på teoretisk datalogi, computergrafik og udviklingsbiologi. - Springer-Verlag, 1992. - ISBN 978-3-540-55320-5 .
  • D.S. Ebert, F.K. Musgrave, D. Peachey, K. Perlin. Teksturering og modellering: En proceduremæssig tilgang. - Academic Press, 1994. - ISBN 0-12-228730-4 .
  • Burry, Jane, Burry Mark. Arkitekturens nye matematik. — New York: Thames og Hudson, 2010.
  • Aristid Lindenmayer. Matematiske modeller for cellulær interaktion i udvikling // J. Theoret. Biologi. - 1968. - Udgave. 18 . - S. 280-315 .
  • P. prusinkiewicz. Proceedings of Graphics Interface '86 / Vision Interface '86. - 1986. - S. 247−253 ..
  • Håndbog i formelle sprog / G.Rozenberg, A.Salomaa. - Springer, 1997. - V. 1 (Ord, sprog, grammatik). - S. 253-328. - ISBN 978-3-642-63863-3 .
  • Stelios Manousakis. Musikalske L-systemer. - Haag: Det Kongelige Konservatorium, 2006. - (Kandidatspeciale - Sonologi).

Links