Sistema di Lindenmayer

Un sistema Lindenmayer, o sistema-L (dall'inglese L-system), è un sistema di riscrittura parallelo e un tipo di grammatica formale. Un sistema-L consiste di un alfabeto di simboli che possano essere usati per creare stringhe, una serie di regole di produzione che espandono ciascun simbolo in una più grande stringa di simboli, una stringa iniziale di "assioma" da cui iniziare la costruzione e un meccanismo per tradurre le stringhe generate in strutture geometriche. In pratica partendo da un oggetto x dell'insieme E, vi applichiamo una funzione otteniamo la sequenza di oggetti di E nel passaggio 1 che denotiamo con . Quindi sostituiamo ogni oggetto di con la trasformazione risultante dalla stessa ottenendo la continuazione nel passaggio 2 denotato con . Ripetiamo questo processo all'infinito, finché non otteniamo una sequenza infinita S.[1] I sistemi di Lindenmayer sono stati introdotti e sviluppati nel 1968 da Aristid Lindenmayer, un biologo teorico ungherese e botanico all'Università di Utrecht. Lindenmayer ha usato sistemi-L per descrivere il comportamento delle cellule vegetali e per modellare i processi di crescita dello sviluppo delle piante. Questi sistemi sono anche stati usati per modellare la morfologia di una varietà di organismi[2] e possono essere usati per generare frattali auto-simili. La differenza essenziale tra le grammatiche di Chomsky e i sistemi-L sta nel metodo di applicazione delle produzioni. Nelle grammatiche di Chomsky le produzioni vengono applicate in sequenza, mentre nei sistemi L vengono applicate in parallelo e contemporaneamente sostituiscono tutte le lettere in una determinata parola. Questa differenza riflette la motivazione biologica dei sistemi di Lindenmayer. Le produzioni hanno lo scopo di catturare le divisioni cellulari negli organismi multicellulari, dove possono verificarsi molte divisioni allo stesso tempo.[3]

Fractal tree (Plate b - 2).jpg

StoriaModifica

Come biologo, Lindenmayer ha lavorato con lieviti e funghi filamentosi e ha studiato i modelli di crescita di vari tipi di batteri, come i cianobatteri Anabaena catenula. Originariamente i sistemi-L sono stati ideati per fornire una descrizione formale dello sviluppo di tali organismi multicellulari semplici e per illustrare le relazioni di vicinato tra le cellule vegetali. L'enfasi era sulle relazioni spaziali tra cellule o moduli di piante più grandi. Il lavoro originale (1968) era limitato a un modello topologico di base.[4] Successivamente, sono state proposte diverse interpretazioni geometriche dei sistem-L al fine di trasformarle in uno strumento più versatile per la modellazione di intere topologie di impianto. La Turtle Geometry, ad esempio, si è dimostrata particolarmente utile.[5] Seguirono i primi risultati nella modellazione di piante superiori (Frijters e Lindenmayer 1974) e (Hogeweg e Hesper 1974).[6][7] In entrambi i casi, è stata impiegata un'interpretazione grafica più sofisticata che ha permesso di modellare la topologia della ramificazione delle piante. Gli aspetti più geometrici, come le lunghezze degli steli (e loro segmenti) e l'angolazione delle ramificazioni tra di loro e lo stelo, sono stati aggiunti in fase di post-elaborazione. Estendendo il lavoro di Hogeweg e Hesper, Smith dimostrerà poi il potenziale di questi sistemi per la sintesi di immagini realistiche.[8][9] Utilizzando tecniche come la codifica della catena si è perfezionata una geometria per rappresentare le immagini e si è dimostrato che i sistemi DOL molto semplici possono generare curve frattali[10]. Questo lavoro è stato esteso da Dekking, che ha esplorato le proprietà limite delle curve generate dai sistemi di Lindenmayer e la dimensione di Hausdorff del limite impostato[11][12]. Contemporaneamente si sono individuati sistemi-L che generano curve classiche di riempimento dello spazio.[13]

EsempiModifica

Esempio: albero frattale (codice binario)Modifica

variabili: 0, 1
costanti: [,]
assioma: 0
regole di produzione: (1 → 11), (0 → 1 [0] 0)

La forma è costruita per ricorsione partendo dall'assioma (in pratica la stringa di partenza) attraverso le regole di produzione che utilizzano le variabili. Ogni carattere della stringa di input viene confrontato con l'elenco delle regole per determinare il carattere o la stringa con cui sostituirlo nella stringa di output. In questo esempio, un '1' nella stringa di input diventa '11' nella stringa di output, mentre '[' rimane lo stesso essendo una costante non sottoposta a sostituzione dalle regole. Applicando questo all'assioma di '0', otteniamo:

assioma: || 0
1^ricorsione: || 1[0]0
2^ricorsione: || 11[1[0]0]1[0]0
3^ricorsione: || 1111[11[1[0]0]1[0]0]11[1[0]0]1[0]0

Possiamo vedere che questa stringa cresce rapidamente in dimensioni e complessità. Questa stringa può essere convertita in un'immagine usando la grafica della tartaruga, in cui a ciascun simbolo viene assegnata un'operazione grafica da eseguire alla “tartaruga” (di fatto un robottino con una penna che si muove seguendo indicazioni di tipo «vai avanti», «gira a destra», «solleva la penna e vai avanti», e così via.) . Ad esempio, nell'esempio sopra, alla tartaruga possono essere date le seguenti istruzioni:

  • 0: disegna un segmento di linea che termina con una foglia
  • 1: disegna un segmento di linea
  • [: push della posizione e dell'angolo, gira a sinistra di 45°
  • ]: pop della posizione e dell'angolo, gira a destra di 45°

Il push (scrivi in memoria) e il pop (tira fuori l’ultima scrittura in memoria) (si riferiscono a uno stack LIFO. Quando l'interpretazione della tartaruga incontra un '[', la posizione corrente e l'angolo vengono salvati e vengono ripristinati quando l'interpretazione incontra un ']' (quindi dall'esempio sopra [0] si può leggere ([) salva posizione gira a sinistra (0) fai un segmento con foglia ]torna all'ultima posizione salvata). Se più valori sono stati "spinti" (push), un "pop" ripristina i valori salvati più di recente. Applicando le regole grafiche elencate sopra alla precedente ricorsione, otteniamo:

Esempio2 2: Alga (codice originale)Modifica

Ecco un esempio più semplice, simile al lavoro originale di Lindenmayer, per descrivere la simulazione della crescita di un'alga:

variabili: A B
costanti: nessuna
assioma: A
regole di produzione: (A → AB), (B → A)

da cui si ottiene:

n = 0 : A
n = 1 : AB
n = 2 : ABA
n = 3 : ABAAB
n = 4 : ABAABABA
n = 5 : ABAABABAABAAB
n = 6 : ABAABABAABAABABAABABA
n = 7 : ABAABABAABAABABAABABAABAABABAABAAB

Infatti:

n=0:         A
            / \
n=1:       A   B
          /|    \
n=2:     A B     A
        /| |     |\
n=3:   A B A     A B
      /| | |\    |\ \
n=4: A B A A B   A B A
             ...
             ...

NoteModifica

  1. ^ https://www.mathcurve.com/fractals/lsysteme/lsysteme.shtml
  2. ^ Grzegorz Rozenberg and Arto Salomaa. The mathematical theory of L systems (Academic Press, New York, 1980). ISBN 0-12-597140-0
  3. ^ PROCEDURAL COMPOSITION TUTORIAL, L-Systems: Some History, su avatar.com.au.
  4. ^ A. Lindenmayer. Mathematical models for cellular interaction in development, Parts I and II. Journal of Theoretical Biology,' 18:280-315,. 1968
  5. ^ P. Prusinkiewicz. Graphical applications of L-systems. In Proceedings of Graphics Interface '86 -- Vision Interface '86, pages 247-253. CIPS, 1986.
  6. ^ D. Frijters and A. Lindenmayer. A model for the growth and flowering of Aster novae-angliae on the basis of table (l,O)L-systems. In G. Rozenberg and A. Salomaa, editors, L Systems, Lecture Notes in Computer Science 15, pages 24-52. Springer-Verlag, Berlin, 1974
  7. ^ P. Hogeweg and B. Hesper. A model study on biomorphological description. Pattern Recognition, 6:165-179, 1974.
  8. ^ A.R. Smith. Plants, fractals, and formal languages. Proceedings of SIGGRAPH '84 (Minneapolis, Minnesota, July 22-27, 1984) in Computer Graphics, 1=8, 3 (July 1984), pages 1-10, ACM SIG-GRAPH, New York, 1984
  9. ^ A.R. Smith. About the cover: Reconfigurable machines. Computer, 11(7):3-4, 1978
  10. ^ B.B. Mandelbrot. The fractal geometry of nature. W.H. Freeman, San Francisco, 1982.
  11. ^ F.M. Dekking. Recurrent sets. Advances in Mathematics, 44(1):78-104, 1982.
  12. ^ F.M. Dekking. Recurrent sets: A fractal formalism. Report 82-32, Delft University of Technology, 1982
  13. ^ R. Siromoney and K.G. Subramanian. Space-filling curves and infinite graphs. In H. Ehrig, M. Nagl, and G. Rozenberg, editors, Graph grammars and their application to computer science; Second International Workshop, Lecture Notes in Computer Science 153, pages 380-391. Springer-Verlag, Berlin, 1983.

Altri progettiModifica

Controllo di autoritàLCCN (ENsh85073593 · GND (DE4074246-5