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 $f:$ otteniamo la sequenza di oggetti di E nel passaggio 1 che denotiamo con $S_{1}$. Quindi sostituiamo ogni oggetto di $S_{1}$ con la trasformazione risultante dalla stessa $f$ ottenendo la continuazione nel passaggio 2 denotato con $S_{2}$. Ripetiamo questo processo all'infinito, finché non otteniamo una sequenza infinita S. 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 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.

Storia

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. 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. Seguirono i primi risultati nella modellazione di piante superiori (Frijters e Lindenmayer 1974) e (Hogeweg e Hesper 1974). 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. 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. 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. Contemporaneamente si sono individuati sistemi-L che generano curve classiche di riempimento dello spazio.

Esempi

Esempio 1: albero frattale (codice binario)

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:

Esempio 2: Alga (codice originale)

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
             ...
             ...

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su Sistema di Lindenmayer