WikiSysop: bnz

2022-03-23T04:14:31Z

bnz

←Starija inačica		Inačica od 23. ožujak 2022. u 04:14
Redak 1:		Redak 1:
	~~<!--'''L-sustav'''-->'''~~L-sustav''' ili '''Lindenmayerov sustav''' je [[formalna gramatika]] koja je najpoznatija po primjeni u modeliranju rasta procesa razvoja [[biljka\|biljaka]], ali i za modeliranje morfologije raznih organizama. L-sustavi se mogu rabiti za generiranje samosličnih fraktala kao što su [[sustav iterirane funkcije\|sustavi iteriranih funkcija]]. L-sustave je uveo i razvio [[1968.]] mađarski teoretski [[biolog]] i [[botaničar]] sa [[Sveučilište u Utrechtz\|Sveučilišta u Utrechtu]], [[Aristid Lindenmayer]] ([[1925.]]–[[1989.]]).		L-sustav''' ili '''Lindenmayerov sustav''' je [[formalna gramatika]] koja je najpoznatija po primjeni u modeliranju rasta procesa razvoja [[biljka\|biljaka]], ali i za modeliranje morfologije raznih organizama. L-sustavi se mogu rabiti za generiranje samosličnih fraktala kao što su [[sustav iterirane funkcije\|sustavi iteriranih funkcija]]. L-sustave je uveo i razvio [[1968.]] mađarski teoretski [[biolog]] i [[botaničar]] sa [[Sveučilište u Utrechtz\|Sveučilišta u Utrechtu]], [[Aristid Lindenmayer]] ([[1925.]]–[[1989.]]).

	== Porijeklo ==		== Porijeklo ==

WikiSysop: no summary specified

2021-11-02T07:25:39Z

no summary specified

←Starija inačica		Inačica od 2. studeni 2021. u 07:25
Redak 202:		Redak 202:

	== Vidjeti također ==		== Vidjeti također ==
	~~{{commonscat\|L-Systems}}~~
	* [[Graftal]]		* [[Graftal]]
	* [[Fraktal]]		* [[Fraktal]]

WikiSysop: Bot: Automatski unos stranica

2021-08-23T03:18:20Z

Bot: Automatski unos stranica

Nova stranica

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

== Porijeklo ==
[[Datoteka:Fractal weeds.jpg|mini|300px|'Travke', generirano L-sustavom u 3D.]]
Kao biolog, Lindenmayer je radio sa [[kvasac|kvascem]] i nitastim [[gljiva]]ma 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 ==

[[Rekurzija|Rekurzivna priroda]] L-sustava vodi ka [[samosličnost]]i i stoga [[fraktal]]nim 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 [[umjetni život|umjetnog života]].

Gramatike L-sustava su vrlo slične [[semi-Thue gramatika|semi-Thue gramatici]] (vidi [[Chomskyjeva hijerarhija|Chomskyjevu hijerarhiju]]). L-sustavi su danas uobičajeno poznati kao ''parametarski'' L sustavi definirani [[n-torka|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 [[stanje (računarstvo)|stanja]]. Što je moguće više pravila se primjenjuje simultano, po iteraciji - ovo je istaknuto svojstvo koje L-sustav razlikuje od [[formalni jezik|formalnog jezika]] generiranog [[gramatika|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 [[prefiksna gramatika|prefiksnom gramatikom]] ili [[regularna gramatika|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 [[Logo (programski jezik)|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 [[alge|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 [[zlatni rez|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]] ===
[[Datoteka:Cantor set in seven iterations.svg|450px|right]]
: '''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 skup|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: [[Datoteka:square koch 0.png|Kochov kvadrat - 0 iteracija]]
<blockquote><blockquote>F</blockquote></blockquote>

: ''n'' = 1: [[Datoteka:square koch 1.png|Kochov kvadrat - 1 iteracija]]
<blockquote><blockquote>F+F-F-F+F</blockquote></blockquote>

: ''n'' = 2: [[Datoteka:square koch 2.png|Kochov kvadrat - 2 iteracije]]
<blockquote><blockquote>F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F</blockquote></blockquote>

: ''n'' = 3: [[Datoteka:square koch 3.png|Kochov kvadrat - 3 iteracije]]

<blockquote><blockquote>F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+
F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F-
F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F-
F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+
F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F</blockquote></blockquote>

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

[[Datoteka:penam01c.gif|centre]]
[[Datoteka:penam02c.gif|centre]]

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:

[[Datoteka:pend05c.gif|centre]]

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

[[Datoteka:pendx05c.gif|centre]]

=== Primjer 6: [[Trokut Sierpinskog|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).

[[Datoteka:Serpinski Lsystem.svg|centre]]
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.

[[Datoteka:Dragon curve L-system.svg|centre|400px]]
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 ''']'''.

[[Datoteka:Fractal-plant.svg|centre]]
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 [[Kochova pahuljica|Kochove krivulje]].

[[Datoteka:Kochsnowflake algorith modified.jpg|centre|300px]]

== 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 [[realni broj|realnoj liniji]] '''R''':
*[[Prouhet-Thue-Morse sustav]]

Dobro poznati L-sustavi na ravnini '''R'''2 su:
* [[prostorno popunjuća krivulja|prostorno popunjuće krivulje]], ([[Hilbertova krivulja]], [[Peanova krivulja]], Dekkingova crkva, [[kolam]]i),
* [[medijan]] prostorno popunjuće krivulje ([[Lévyjeva C krivulja]], [[zmajolika 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]] [http://algorithmicbotany.org/papers/#abop besplatno dostupna PDF verzija]

== Vidjeti također ==
{{commonscat|L-Systems}}
* [[Graftal]]
* [[Fraktal]]
* [[Sustav iterirane funkcije]]
* [[Hilbertova krivulja]]
* [[Prepisivanje stringa]]

== Vanjske poveznice ==
* [http://www.math.okstate.edu/mathdept/dynamics/lecnotes/node12.html#SECTION00040000000000000000 David J. Wrightov članak o L-sustavima]

* [http://algorithmicbotany.org/ Algoritamska botanika na Sveučilištu Calgary]
* [http://spanky.triumf.ca/www/fractint/lsys/truefractal.html Fractint L-System True Fractals]
*[http://www.biologie.uni-hamburg.de/b-online/e28_3/lsys.html "An introduction to Lindenmayer systems", by Gabriela Ochoa]. Brief description of L-systems and how the strings they generate can be interpreted by computer.
*[http://sourceforge.net/projects/pplant/ "powerPlant" an open-source landscape modelling software]
*[http://www.mizuno.org/applet/branching/ "Branching: L-system Tree" using Java applet]
* [http://spanky.triumf.ca/www/fractint/fractint.html ''Fractint'' home page]
* [http://www.mh-portfolio.com/lsystems.html L-Systems in Architecture]
* [http://www.generation5.org/content/2002/lse.asp A simple L-systems generator (Windows)]
* [http://www.lab4web.com/chelmiger/lyndyhop/ Lyndyhop: another simple L-systems generator (Windows & Mac)]
* [http://www.cs.ucl.ac.uk/staff/W.Langdon/pfeiffer.html An evolutionary L-systems generator (anyos*)]
* [http://fractint.oblivion.cz./ L-systems gallery – a tribute to Fractint]
*[http://www.pawfal.org/index.php?page=LsystemComposition "LsystemComposition"]. Page at Pawfal ("poor artists working for a living") about using L-systems and [[genetic algorithms]] to generate music.
*[http://www.grogra.de/ eXtended L-Systems (XL), Relational Growth Grammars, and open-source software platform GroIMP.]
*[http://to-campos.planetaclix.pt/fractal/plantae.htm A JAVA applet with many fractal figures generated by L-systems.]
*[https://web.archive.org/web/20091027012517/http://uk.geocities.com/joelewisbowen/lsystem.html Another L-system applet, supporting programming, with explanation and examples.]
*[http://www.arch.columbia.edu/Students/Fall2003/Cheng.Chih-Wei/ L-systems in Architecture; genetic housing.]
*[http://www.somporn.net/ L-systems in Plant Growth,Simulation and Visualization (PlantVR).]
*[http://www.koncon.nl/public_site/220/Sononieuw/NL/thesis-pdf/Stelios%20Manousakis-Musical%20L-systems.pdf Musical L-systems: Theory and applications about using L-systems to generate musical structures, from waveforms to macro-forms.]
*[http://lsysjs.qwert.ch/ LSys/JS] - Interactive L-System interpreter using the [[Canvas (HTML element)|Canvas HTML element]].
*[http://www.qwerkop.de/qwerkop-projects-lsystem.php/ Lindenmayer System for plant visualisation (Java Applet)].
*[http://cs.unm.edu/~joel/PaperFoldingFractal/paper.html Fractal Grower: Free Java paper folding L-System intended for elementary and middle school students.]
*[http://www.cove.org/default.aspx?id=1&sid=3&mid=2 Programmatic animations in actionscript showing various L-systems.]
[[Kategorija:Formalni jezici]]
[[Kategorija:Fraktali]]

L-sustav - Povijest promjena

WikiSysop: bnz

WikiSysop: no summary specified

WikiSysop: Bot: Automatski unos stranica