L-sustav

Izvor: Wikipedija
Skoči na: orijentacija, traži

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[uredi VE | uredi]

'Travke', generirano L-sustavom u 3D.

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[uredi VE | uredi]

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[uredi VE | uredi]

Primjer 1: Alge[uredi VE | uredi]

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[uredi VE | uredi]

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[uredi VE | uredi]

Cantor set in seven iterations.svg
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[uredi VE | uredi]

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: Kochov kvadrat - 0 iteracija

F

n = 1: Kochov kvadrat - 1 iteracija

F+F-F-F+F

n = 2: Kochov kvadrat - 2 iteracije

F+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: Kochov kvadrat - 3 iteracije

F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+

F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F- F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F- F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+

F+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[uredi VE | uredi]

Sljedeće su slike generirane L-sustavom. Srodne su i slične Penroseovim popločanjima, koje je izmislio Roger Penrose.

Penam01c.gif
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:

Pend05c.gif

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

Pendx05c.gif

Primjer 6: Sierpinskijev trokut[uredi VE | uredi]

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

Serpinski Lsystem.svg

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

Primjer 7: Zmajolika krivulja[uredi VE | uredi]

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.

Dragon curve L-system.svg

Zmajolika krivulja za n = 10

Primjer 8: Fraktalna biljka[uredi VE | uredi]

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

Fractal-plant.svg

Fraktalna biljka za n = 6

Primjer 9: Modificirani Kochov L-sustav[uredi VE | uredi]

Fraktalna figura nacrtana uvođenjem periodičke promjene predznaka kuta u iteraciji običnog L-sustava Kochove krivulje.

Kochsnowflake algorith modified.jpg

Otvoreni problemi[uredi VE | uredi]

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[uredi VE | uredi]

L-sustavi na realnoj liniji R:

Dobro poznati L-sustavi na ravnini R2 su:

Knjige[uredi VE | uredi]

Vidjeti također[uredi VE | uredi]

Logotip Zajedničkog poslužitelja
Na Zajedničkom poslužitelju postoje datoteke vezane uz: L-sustav

Vanjske poveznice[uredi VE | uredi]