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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Fractal_weeds.jpg/300px-Fractal_weeds.jpg)
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) je skup simbola koji sadrže elemente koji mogu biti zamijenjeni (varijable)
- S je skup simbola koji sadrže elemente koji ostaju fiksirani (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 tzv. 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: 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: Cantorova prašina
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/56/Cantor_set_in_seven_iterations.svg/450px-Cantor_set_in_seven_iterations.svg.png)
- 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 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.
![](http://upload.wikimedia.org/wikipedia/commons/6/6a/Penam01c.gif)
![](http://upload.wikimedia.org/wikipedia/commons/2/21/Penam02c.gif)
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:
![](http://upload.wikimedia.org/wikipedia/commons/9/98/Pend05c.gif)
inače dobijemo uzorke koji ne pokrivaju u potpunosti beskonačnu površinu:
![](http://upload.wikimedia.org/wikipedia/commons/4/4b/Pendx05c.gif)
Primjer 6: 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).
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/23/Serpinski_Lsystem.svg/486px-Serpinski_Lsystem.svg.png)
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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/11/Dragon_curve_L-system.svg/400px-Dragon_curve_L-system.svg.png)
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 ].
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/44/Fractal-plant.svg/453px-Fractal-plant.svg.png)
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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/79/Kochsnowflake_algorith_modified.jpg/300px-Kochsnowflake_algorith_modified.jpg)
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 R2 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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/15px-Commons-logo.svg.png)
Eksterni linkovi
- David J. Wrightov članak o L-sustavima Arhivirano 2008-12-25 na Wayback Machine-u
- Algoritamska botanika na Sveučilištu Calgary
- Fractint L-System True Fractals Arhivirano 2002-05-03 na Wayback Machine-u
- "An introduction to Lindenmayer systems", by Gabriela Ochoa Arhivirano 2009-03-26 na Wayback Machine-u. 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 Arhivirano 2008-05-06 na Wayback Machine-u
- L-Systems in Architecture
- A simple L-systems generator (Windows) Arhivirano 2003-12-20 na Wayback Machine-u
- Lyndyhop: another simple L-systems generator (Windows & Mac) Arhivirano 2008-12-04 na Wayback Machine-u
- An evolutionary L-systems generator (anyos*)
- L-systems gallery – a tribute to Fractint
- "LsystemComposition" Arhivirano 2010-06-16 na Wayback Machine-u. 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. Arhivirano 2016-08-06 na Wayback Machine-u
- Another L-system applet, supporting programming, with explanation and examples.
- L-systems in Architecture; genetic housing. Arhivirano 2009-02-25 na Wayback Machine-u
- 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. Arhivirano 2006-10-01 na Wayback Machine-u
- LSys/JS Arhivirano 2009-02-01 na Wayback Machine-u - Interactive L-System interpreter using the Canvas HTML element.
- Lindenmayer System for plant visualisation (Java Applet) Arhivirano 2007-07-17 na Wayback Machine-u.
- Fractal Grower: Free Java paper folding L-System intended for elementary and middle school students.
- Programmatic animations in actionscript showing various L-systems. Arhivirano 2007-06-02 na Wayback Machine-u