L-sustav iliLindenmayerov sustav jeformalna gramatika koja je najpoznatija po primjeni u modeliranju rasta procesa razvojabiljaka, ali i za modeliranje morfologije raznih organizama. L-sustavi se mogu rabiti za generiranje samosličnih fraktala kao što susustavi iteriranih funkcija. L-sustave je uveo i razvio1968. mađarski teoretskibiolog ibotaničar saSveučilišta u Utrechtu,Aristid Lindenmayer (1925.–1989.).
Kao biolog, Lindenmayer je radio sakvascem i nitastimgljivama te proučavao uzorke rasta raznih vrsta algi, kao što su modrozelene algeAnabaena 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.
Rekurzivna priroda L-sustava vodi kasamosličnosti i stogafraktalnim 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 generiranjuumjetnog života.
Gramatike L-sustava su vrlo sličnesemi-Thue gramatici (vidiChomskyjevu hijerarhiju). L-sustavi su danas uobičajeno poznati kaoparametarski L sustavi definiranin-torkom:
gdje je
Pravila se gramatike L-sustava primjenjuju iterativno počinjući od inicijalnogstanja. Što je moguće više pravila se primjenjuje simultano, po iteraciji - ovo je istaknuto svojstvo koje L-sustav razlikuje odformalnog jezika generiranoggramatikom. 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 jekontekstno neovisan ako se svako produkcijsko pravilo odnosi samo na pojedinačni simbol, ne i na njegove susjede. Kontekstno neovisni L-sustavi se toga specificiraju iliprefiksnom gramatikom iliregularnom gramatikom.
Ako pravilo ovisi ne samo o jednom simbolu već i o njegovim susjedima, tada je naslovljenkontekstno ovisnim L-sustavom.
Ako postoji točno jedna produkcija za svaki simbol, za L-sustav se kaže da jedeterministički (deterministički kontekstno neovisni L-sustav se popularno zoveDOL-sustav). Ako postoji nekoliko produkcija, i svaka je odabrana određenom vjerojatnošću pri svakoj iteraciji, tada se radi ostohastič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, programFractInt (vidi vanjske poveznice dolje) koristiturtle grafiku (sličnu onoj uprogramskom jeziku Logo) za iscrtavanje slika na zaslonu. Interpretira svaku konstantu L-sustava kao naredbu zaturtle (trokutasti kursor na zaslonu).
Lindenmayerov izvorni L-sustav za modeliranje rastaalgi.
što pak generira:
Ako definiramo sljedeću jednostavnu gramatiku:
tada ovaj L-sustav generira sljedeći slijed stringova:
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 poznatiFibonaccijev slijed brojeva:
Za n>0, ako brojimok-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šekratnikzlatnog 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).
NekaA znači "crtaj naprijed" iB znači "pomakni naprijed".
Ovo generira poznatovCantorov fraktalni skup za realnu ravnu linijuR.
Varijanta Kochove krivulje koja koristi samo prave kutove.
Ovdje,F znači "crtaj naprijed",+ znači "zakreni ulijevo za 90°", i- znači "zakreni udesno za 90°"
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+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
Sljedeće su slike generirane L-sustavom. Srodne su i slične Penroseovim popločanjima, koje je izmislioRoger Penrose.
Kao L-sustav ova se popločanja zovuPenroseovi rombovi iPenroseove ploče. Gornje slike su generirane zan = 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:
Trokut Sierpińskog nacrtan koristeći L-sustav.
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 zan = 2,n = 4,n = 6,n = 9
Zmajolika krivulja nacrtana koristeći L-sustav.
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 zan = 10
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 zan = 6
Fraktalna figura nacrtana uvođenjem periodičke promjene predznaka kuta u iteraciji običnog L-sustavaKochove krivulje.
Postoje mnogi otvoreni problemi koji uključuju proučavanje L-sustava. Na primjer:
L-sustavi narealnoj linijiR:
Dobro poznati L-sustavi na ravniniR2 su:
