L-sistem

**L-sustav** ili **Lindenmayerov sustav** je formalna gramatika koja je najpoznatija po primjeni u modeliranju rasta procesa razvoja biljaka, ali i za modeliranje morfologije raznih organizama. L-sustavi se mogu rabiti za generiranje samosličnih fraktala kao što su sustavi iteriranih funkcija. L-sustave je uveo i razvio 1968. mađarski teoretski biolog i botaničar sa Sveučilišta u Utrechtu, Aristid Lindenmayer (1925.–1989.).

## Porijeklo

Kao biolog, Lindenmayer je radio sa kvascem i nitastim gljivama te proučavao uzorke rasta raznih vrsta algi, kao što su modrozelene alge *Anabaena catenula*. Izvorno su L-sustavi izvedeni za pružanje formalnog opisa razvoja takvih jednostavnih višestaničnih organizama, kao i da bi se ilustrirali odnosi susjedstva među biljnim stanicama. Kasnije, ovaj je sustav proširen kako bi opisao više biljke i složene strukture grananja.

## Struktura L-sustava
Rekurzivna priroda L-sustava vodi ka samosličnosti i stoga fraktalnim oblicima koji se lako opisuju L-sustavom. Modeli biljaka i izgledom prirodnih organskih oblika se slično lako definiraju, a kako se dubina rekruzije povećava, oblik polako 'raste' i postaje složeniji. Lindemayerovi sustavi su također popularni u generiranju umjetnog života.

Gramatike L-sustava su vrlo slične semi-Thue gramatici (vidi Chomskyjevu hijerarhiju). L-sustavi su danas uobičajeno poznati kao *parametarski* L sustavi definirani n-torkom:

:**G** = {*V*, *S*, ω, *P*},

gdje je
* **V** (*[[abeceda (računarstvo)|abeceda]]*) je skup simbola koji sadrže elemente koji mogu biti zamijenjeni (*[[nezavršni simbol|varijable]]*)
* **S** je skup simbola koji sadrže elemente koji ostaju fiksirani (*[[završni simbol|konstante]]*)
* **ω** (*početak*, *aksiom* ili *inicijator*) je niz simbola iz **V** koji definiraju inicijalno stanje sustava
* **P** je skup *pravila produkcija* ili *produkcija* koje definiraju način na koji varijable mogu biti zamijenjene konstantama i drugim varijablama. Produkcija se sastoji od dva stringa - *prethodnika* i *sljedbenika*.

Pravila se gramatike L-sustava primjenjuju iterativno počinjući od inicijalnog stanja. Što je moguće više pravila se primjenjuje simultano, po iteraciji - ovo je istaknuto svojstvo koje L-sustav razlikuje od formalnog jezika generiranog gramatikom. Ako bi se produkcijska pravila primjenjivala tek jedan po jedan, stvorio bi se tek jezik, mjesto L-sustava. Stoga su L-sustavi strogi podskupovi jezika.

L-sustav je *kontekstno neovisan* ako se svako produkcijsko pravilo odnosi samo na pojedinačni simbol, ne i na njegove susjede. Kontekstno neovisni L-sustavi se toga specificiraju ili prefiksnom gramatikom ili regularnom gramatikom.

Ako pravilo ovisi ne samo o jednom simbolu već i o njegovim susjedima, tada je naslovljen *kontekstno ovisnim* L-sustavom.

Ako postoji točno jedna produkcija za svaki simbol, za L-sustav se kaže da je *deterministički* (deterministički kontekstno neovisni L-sustav se popularno zove *DOL-sustav*). Ako postoji nekoliko produkcija, i svaka je odabrana određenom vjerojatnošću pri svakoj iteraciji, tada se radi o *stohastičkom* L-sustavu.

Rabeći L-sustave za generiranje grafičkih slika zahtijeva da se simboli modela odnose na elemente slike računalnog zaslona. Primjerice, program *FractInt* (vidi vanjske poveznice dolje) koristi *turtle* grafiku (sličnu onoj u programskom jeziku Logo) za iscrtavanje slika na zaslonu. Interpretira svaku konstantu L-sustava kao naredbu za *turtle* (trokutasti kursor na zaslonu).

## Primjeri L-sustava
### Primjer 1: Alge
Lindenmayerov izvorni L-sustav za modeliranje rasta algi.

:**varijable** : A B
:**konstante** : nijedna
:**početak** : A 
:**pravila** : (A → AB), (B → A)

što pak generira:

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

### Primjer 2: [[Fibonaccijev broj|Fibonaccijevi brojevi]]
Ako definiramo sljedeću jednostavnu gramatiku:

: **varijable** : A B
: **konstante** : nijedna
: **početak** : A
: **pravila** : (A → B), (B → AB)

tada ovaj L-sustav generira sljedeći slijed stringova:

: *n* = 0 : A
: *n* = 1 : B
: *n* = 2 : AB
: *n* = 3 : BAB
: *n* = 4 : ABBAB
: *n* = 5 : BABABBAB
: *n* = 6 : ABBABBABABBAB
: *n* = 7 : BABABBABABBABBABABBAB

Ovo su zrcalne slike stringova prvog primjera, sa zamijenjenim A i B. Još jednom, svaki je string nadovezivanje prethodna dva, ali u obrnutom redoslijedu.

U bilo kojem od primjera, ako izračunamo duljnu svakog stringa, dobijemo poznati Fibonaccijev slijed brojeva:

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

Za n>0, ako brojimo *k*-tu poziciju od invarijantnog kraja stringa (lijevo u slučaju prvog primjera i desno u slučaju drugog primjera), vrijednost je određena time potpada li višekratnik zlatnog reza unutar intervala (k-1,k). Omjer A i B stoga konvergira ka zlatnom rezu.

Ovaj primjer daje isti rezultat (u terminima duljine svakog od stringova, ne u slijedovima simbola A i B) ukoliko je pravilo *(B → AB)* zamijenjeno pravilom *(B → BA)*.

### Primjer 3: [[Cantorov skup#Višedimenzionalni Cantorovi skupovi|Cantorova prašina]]

: **varijable** : A B 
: **konstante** : nijedna
: **početak** : A {počinjući znak stringa} 
: **pravila** : (A → ABA), (B → BBB)

Neka *A* znači "crtaj naprijed" i *B* znači "pomakni naprijed".

Ovo generira poznatov Cantorov fraktalni skup za realnu ravnu liniju **R**.

### Primjer 4: [[Kochova pahuljica|Kochova krivulja]]
Varijanta Kochove krivulje koja koristi samo prave kutove.

: **varijable** : F 
: **konstante** : + −
: **početak** : F 
: **pravila** : (F → F+F−F−F+F)

Ovdje, *F* znači "crtaj naprijed", *+* znači "zakreni ulijevo za 90°", i *-* znači "zakreni udesno za 90°"

: *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

### Primjer 5: [[Penroseova popločanja]]
Sljedeće su slike generirane L-sustavom. Srodne su i slične Penroseovim popločanjima, koje je izmislio Roger Penrose.

      
     

Kao L-sustav ova se popločanja zovu *Penroseovi rombovi* i *Penroseove ploče*. Gornje slike su generirane za *n* = 6 kao L-sustav.
Ako pravilno položimo Penroseove ploče kao L-sustav, dobijemo sljedeće popločanje:

     

inače dobijemo uzorke koji ne pokrivaju u potpunosti beskonačnu površinu:

     

### Primjer 6: [[Trokut Sierpińskog|Sierpinskijev trokut]]
Trokut Sierpińskog nacrtan koristeći L-sustav.

: **varijable** : A B 
: **konstante** : + −
: **početak** : A 
: **pravila** : (A → B−A−B),(B → A+B+A)
: **kut** : 60º

Ovdje, A i B znači "crtaj naprijed", + znači "zakreni ulijevo kutom", i - znači "zakreni udesno kutom". Kut mijenja predznak svake iteracije tako da su baze trokutastih oblika uvijek na dnu (inače bi bile na dnu i vrhu naizmjenice).

Evolucija za *n* = 2, *n* = 4, *n* = 6, *n* = 9

### Primjer 7: [[Zmajolika krivulja]]
Zmajolika krivulja nacrtana koristeći L-sustav.

: **varijable** : X Y F 
: **konstante** : + −
: **početak** : FX 
: **pravila** : (X → X+YF+),(Y → -FX-Y)
: **kut** : 90º

Ovdje, F znači "crtaj naprijed", - znači "zakreni ulijevo za 90°", i + znači "zakreni udesno za 90°". X i Y ne odgovaraju nijednoj akciiji crtanja i korišteni su samo za upravljanje evolucijom krivulje.

Zmajolika krivulja za *n* = 10

### Primjer 8: Fraktalna biljka
: **varijable** : X F 
: **konstante** : + −
: **početak** : X 
: **pravila** : (X → F-X+X]+F[+FX]-X),(F → FF)
: **kut** : 25º

Ovdje, F znači "nacrtaj naprijed", - znači "zakreni ulijevo za 25º" i + znači "zakreni udesno za 25º". X ne odgovara nijednoj akciji crtanja i rabi se za upravljanje evolucijom krivulje. **[** odgovara spremanju trenutnih vrijednosti za poziciju i kut, koje se vraćaju izvršavanjem odgovarajućeg **]**.

Fraktalna biljka za *n* = 6

### Primjer 9: Modificirani Kochov L-sustav
Fraktalna figura nacrtana uvođenjem periodičke promjene predznaka kuta u iteraciji običnog L-sustava Kochove krivulje.

## Otvoreni problemi
Postoje mnogi otvoreni problemi koji uključuju proučavanje L-sustava. Na primjer:
* Karakterizacija svih determinističkih kontekstno neovisnih L-sustava koji su lokalno nadovezivi (potpuno je rješenje poznato samo u slučaju dvije varijable).
* Za danu strukturu, pronađi L-sustav koji je producira.

## Vrste L-sustava
L-sustavi na realnoj liniji **R**:
* Prouhet-Thue-Morse sustav

Dobro poznati L-sustavi na ravnini **R**2 su: 
* prostorno popunjuće krivulje, (Hilbertova krivulja, Peanova krivulja, Dekkingova crkva, kolami),
* medijan prostorno popunjuće krivulje (Lévyjeva C krivulja, Harter-Heighway zmajolika krivulja, Davis-Knuth terdragon), 
* popločanja (sfingino popločanje, Penroseovo popločanje),
* stabla, biljke i slično.

## Knjige
* Przemyslaw Prusinkiewicz - The Algorithmic Beauty of Plants besplatno dostupna PDF verzija

## Povezano

* Fraktal
* Sustav iterirane funkcije
* Hilbertova krivulja

## Vanjske veze
* David J. Wrightov članak o L-sustavima 
* Algoritamska botanika na Sveučilištu Calgary
* Fractint L-System True Fractals 
* "An introduction to Lindenmayer systems", by Gabriela Ochoa . Brief description of L-systems and how the strings they generate can be interpreted by computer.
* "powerPlant" an open-source landscape modelling software
* "Branching: L-system Tree" using Java applet
* ''Fractint'' home page 
* L-Systems in Architecture 
* A simple L-systems generator (Windows) 
* Lyndyhop: another simple L-systems generator (Windows & Mac) 
* An evolutionary L-systems generator (anyos*)
* L-systems gallery – a tribute to Fractint
* "LsystemComposition" . Page at Pawfal ("poor artists working for a living") about using L-systems and genetic algorithms to generate music. 
* eXtended L-Systems (XL), Relational Growth Grammars, and open-source software platform GroIMP.
* A JAVA applet with many fractal figures generated by L-systems. 
* Another L-system applet, supporting programming, with explanation and examples.
* L-systems in Architecture; genetic housing. 
* L-systems in Plant Growth,Simulation and Visualization (PlantVR).
* Musical L-systems: Theory and applications about using L-systems to generate musical structures, from waveforms to macro-forms. 
* LSys/JS  - Interactive L-System interpreter using the Canvas HTML element.
* Lindenmayer System for plant visualisation (Java Applet) .
* Fractal Grower: Free Java paper folding L-System intended for elementary and middle school students.
* Programmatic animations in actionscript showing various L-systems.