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