L-järjestelmä

L-järjestelmä tai Lindenmeier-järjestelmä on rinnakkainen uudelleenkirjoitusjärjestelmä ja eräänlainen muodollinen kielioppi . L-järjestelmä koostuu merkkiaakkosesta, jota voidaan käyttää merkkijonojen luomiseen , joukosta generatiivisia sääntöjä , jotka määrittävät korvaussäännöt jokaiselle merkille, alkumerkkijonosta (" aksiooma "), josta rakentaminen alkaa, ja mekanismista. generoidun merkkijonon muuntamiseksi geometrisiksi rakenteiksi. L-järjestelmän ehdotti ja kehitti vuonna 1968 Aristide Lindenmeier , unkarilainen biologi ja kasvitieteilijä Utrechtin yliopistosta .. Lindenmeier käytti L-järjestelmiä kuvaamaan kasvisolujen käyttäytymistä ja mallintamaan kasvin kehitysprosessia . L-järjestelmiä on käytetty myös erilaisten organismien morfologian mallintamiseen [1] ja niitä voidaan käyttää samankaltaisten fraktaalien , kuten iteroitujen toimintojen järjestelmien, luomiseen .

Origins

Biologina Lindenmeier työskenteli hiivojen ja rihmasienten parissa ja tutki eri levälajien , kuten sinilevän Anabaena catenula , kasvutapoja . Aluksi L-järjestelmiä kehitettiin kuvaamaan muodollisesti tällaisten yksinkertaisten monisoluisten organismien kehitystä ja havainnollistamaan kommunikaatiota viereisten kasvisolujen välillä. Järjestelmää laajennettiin myöhemmin kuvaamaan korkeampia kasveja ja monimutkaisia ​​haarautuvia rakenteita.

L-järjestelmän rakenne

L-järjestelmän sääntöjen rekursiivinen luonne johtaa itsensä samankaltaisuuteen , ja siksi fraktaalimaiset muodot kuvataan helposti L-järjestelmän avulla. Kasvimalleja ja luonnollisen näköisiä orgaanisia muotoja on helppo muodostaa, koska malli hitaasti "kasvaa" ja muuttuu monimutkaisemmaksi rekursion tason kasvaessa. Lindenmeier-järjestelmät ovat suosittuja myös keinotekoisessa elämänmuodostuksessa .

L-järjestelmien kieliopit ovat hyvin samankaltaisia ​​kuin Thue puolijärjestelmät (katso " Chomskyn hierarkia "). L-järjestelmät tunnetaan nykyään parametrisinä L-järjestelminä, jotka määritellään monikkona

G = ( V , ω, P ),

missä

L-järjestelmän kielioppisääntöjä sovelletaan iteratiivisesti aksioomasta (alkutilasta) alkaen. Iteraatiota kohden sovelletaan mahdollisimman monia sääntöjä. Se, että jokaisessa iteraatiossa käytetään mahdollisimman montaa sääntöä, erottaa L-järjestelmän muodollisesta kielioppista luodusta formaalista kielestä , joka soveltaa vain yhtä sääntöä iteraatiota kohden. Jos päättelysääntöjä sovellettaisiin yksi kerrallaan, olisi helppo luoda kieli L-järjestelmän sijaan. L-järjestelmät ovat siis osa kieliä.

L-järjestelmä on kontekstiton, jos jokainen päättelysääntö viittaa vain yksittäisiin merkkeihin, ei niiden naapureihin. Kontekstivapaat L-järjestelmät määritellään yhteydettömän kieliopin avulla . Jos sääntö ei riipu vain yhdestä symbolista, vaan myös viereisistä symboleista, järjestelmää kutsutaan kontekstiherkäksi L-järjestelmäksi.

Jos kullekin symbolille on täsmälleen yksi sääntö, L-järjestelmän sanotaan olevan deterministinen (determinististä kontekstista riippumatonta L-järjestelmää kutsutaan D0L-järjestelmäksi ). Jos sääntöjä on useita ja jokainen niistä valitaan jollain todennäköisyydellä jokaisessa iteraatiossa, niin tämä on stokastinen L-järjestelmä.

L-järjestelmien käyttäminen graafisten kuvien tuottamiseen edellyttää, että mallin symbolit viittaavat tietokoneen näytöllä näkyvän kuvan elementteihin. Esimerkiksi Fractint -ohjelma käyttää kilpikonnagrafiikkaa (samanlainen kuin logokielen grafiikka ) tuottaakseen kuvan näytölle. Ohjelma tulkitsee jokaisen vakion L-järjestelmämallissa kilpikonnagrafiikkajärjestelmän komentoina.

Esimerkkejä L-järjestelmistä

Esimerkki 1: Levät

Lindenmeierin alkuperäinen L-järjestelmä leväkasvun mallintamiseen.

muuttujat  : AB vakiot  : ei aksiooma  : A säännöt  : (A → AB), (B → A)

Järjestelmä antaa

n = 0 : A n = 1: AB n = 2: ABA n = 3: ABAAB n = 4: ABAABABA n = 5: ABAABABAABAAB n = 6: ABAABABAABAABABAABABABA n = 7 : ABAABABAABAABABAABABAABAABABAABAAB Esimerkki 1: Levät, selitys n=0: Alku (aksiooma/aloittaja) / \ n=1: AB alkukerta A muuttuu AB:ksi säännön (A → AB) mukaan, sääntöä (B → A) ei voida soveltaa /| \ n=2: ABA kaikki säännöt koskevat merkkijonoa AB, A:sta tulee jälleen AB ja B:stä A /| | |\ n=3: ABAAB huomaa, että kaikki A:t käännetään kopioksi itsestään ja B lisätään, josta tulee ... /| | |\ |\ \ n=4: ABAABABA ... A:ksi seuraavassa sukupolvessa, mikä johtaa rekursioon

Tuloksena on Fibonacci-sanoja . Jos laskemme jokaisen rivin pituuden, saamme kuuluisan Fibonacci-sekvenssin (ensimmäinen jätetään pois):

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

Jos laskemme kunkin rivin k :nnen sijainnin rivin vasemmasta päästä, arvo riippuu siitä, kuuluuko k -kertainen kultainen suhde väliin . Myös kirjainten A ja B esiintymisten suhde konvergoi kultaiseen leikkaukseen.

Tämä esimerkki antaa saman tuloksen (merkkijonon pituuden, ei kirjainten A ja B sarjan suhteen ), jos sääntö ( A → AB ) korvataan ( A → BA ), mutta saadaan peilattuja merkkijonoja.

Tämä sekvenssi on :n katenantti, koska , missä on n : s sukupolvi.

Esimerkki 2: Pythagoraan puu

  • muuttujat : 0, 1
  • vakiot : [, ]
  • aksiooma : 0
  • säännöt : (1 → 11), (0 → 1[0]0)

Kuvio on rakennettu soveltamalla rekursiivisesti päättelysääntöjä aksioomiin. Jokainen syötemerkkijonon merkki tarkistetaan sääntöluettelosta sen määrittämiseksi, millä merkillä se tulisi korvata. Tässä esimerkissä tulon "1" muuttuu lähdössä "11", mutta "[" ei muutu. Soveltamalla päättelysääntöjä aksioomiin "0", saamme:

aksiooma: 0
1. rekursio: 1[0]0
2. rekursio: 11[1[0]0]1[0]0
3. rekursio: 1111[11[1[0]0]1[0]0]11[1[0]0]1[0]0
…

Näemme merkkijonojen kasvavan nopeasti pituudeltaan ja monimutkaisuudeltaan. Merkkijono voidaan piirtää kuvana käyttämällä kilpikonnagrafiikkaa , jossa jokaisella hahmolla on kilpikonnalle vastaava grafiikkatoiminto. Tässä esimerkissä kilpikonnalle voidaan antaa seuraavat komennot:

  • 0: piirrä lehtiin päättyvä segmentti
  • 1: piirrä viiva
  • [: pinon vetoasento ja kulma, käännä vasemmalle 45 astetta
  • ]: lue sijainti ja kulma pinosta, käännä oikealle 45 astetta

"Push on the pino" ja "pop pois pinosta" viittaavat LIFO-pinoon (yksityiskohtaisempi kielioppi vaatisi jakamista "laita pinoon" ja "käännä"). Kun tulkki kohtaa "[", kilpikonnan nykyinen sijainti ja liikekulma tallennetaan pinoon; kun "]" kohtaa, sijainti ja kulma palautetaan. Jos pinoon työnnetään useita arvoja, viimeksi työnnetty arvo palautetaan. Kirjallisuudessa L-järjestelmiä, jotka käyttävät tätä lähestymistapaa haaroittamiseen, kutsutaan "haarukoiduiksi L-järjestelmiksi" (haarukoidut L-järjestelmät) [2] .

Kun näitä graafisia sääntöjä sovelletaan aiemmin saatuun merkkijonoon, meillä on:

  • Axiom

  • Ensimmäinen rekursio

  • Toinen rekursio

  • Kolmas rekursio

  • Neljäs rekursio

  • Seitsemäs rekursio, kymmenkertaistettu

Esimerkki 3: Cantor set

muuttujat : AB vakiot : ei aloitus : {aloitusjono} säännöt : (A → ABA), (B → BBB)

Tarkoitakoon A "piirtää viiva" ja B tarkoittaa "liikkua".

Tällainen kielioppi muodostaa kuuluisan Cantor-fraktaalijoukon todelliselle akselille R .

Esimerkki 4: Kochin käyrä

Kochin käyrän muunnos , jossa käytetään vain suoria kulmia.

muuttujat  : F vakiot  : + − aloitus  : F säännöt  : (F → F+F−F−F+F)

Tässä F tarkoittaa "piirrä viiva", + tarkoittaa "kiertoa vasemmalle 90°" ja − tarkoittaa "kiertoa oikealle 90°" (katso " Turtle Graphics ").

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

Esimerkki 5: Sierpinskin kolmio

Sierpinskin kolmio , piirretty L-systeemillä.

muuttujat : FG vakiot : + − aloitus : F-G-G sääntö : (F → F−G+F+G−F), (G → GG) kulma : 120°

Tässä F ja G tarkoittavat "vetää viiva", + tarkoittaa "käänny oikealle kulmasta" ja − tarkoittaa "käänny vasemmalle kulmasta".

  • n = 2

  • n = 4

  • n = 6

Voit myös arvioida Sierpinskin kolmion käyttämällä Sierpinskin nuoli-käyrä L-järjestelmää .

muuttujat : AB vakiot : + − aloitus : A säännöt : (A → B−A−B), (B → A+B+A) kulma : 60°

Tässä A ja B tarkoittavat "piirrä viiva", + tarkoittaa "käänny vasemmalle kulmassa" ja − tarkoittaa "käänny oikealle kulmassa" (katso " Kilpikonnagrafiikka ").

Iteraatiot n = 2, n = 4, n = 6, n = 8

Esimerkki 6: Dragon Curve

Dragon Curve , piirretty L-järjestelmällä.

muuttujat  : XY vakiot  : F + − aloitus  : FX säännöt  : (X → X+YF+), (Y → −FX−Y) kulma  : 90°

Tässä F tarkoittaa "piirtää viiva", − tarkoittaa "kääntää vasemmalle 90°" ja + tarkoittaa "kääntää oikealle 90°". X ja Y eivät vastaa mitään piirtotoimintoa, vaan niitä käytetään vain käyrän piirtämiseen.


Iteraatiot n = 10, n = 15

Esimerkki 7: Fraktaalikasvi

muuttujat  : XF vakiot  : + − [ ] aloitus  : X säännöt  : (X → F−[[X]+X]+F[+FX]−X), (F → FF) kulma  : 25°

Tässä F tarkoittaa "piirrä viiva", − tarkoittaa "kiertoa vasemmalle 25°" ja + tarkoittaa "kiertoa oikealle 25°". X ei vastaa mitään piirtotoimintoa, sitä käytetään vain käyrän piirtämiseen. Hakasulke "[" vastaa nykyisen sijainnin ja kulman arvojen tallentamista, jotka palautetaan, kun vastaava "]"-merkki suoritetaan.

Fraktaalikasvi arvolle n = 6

Vaihtoehdot

L-järjestelmätekniikkaan on tehty useita kehityksiä, joita voidaan käyttää yhdessä. Niitä ovat stokastiset kieliopit , kontekstiherkät kieliopit ja parametriset kieliopit.

Stokastiset kieliopit

Juuri tarkastelemamme kielioppimallit ovat deterministisiä. Toisin sanoen mikä tahansa aakkosten merkki on aina valittuna täsmälleen yksi sääntö ja sama korvaus suoritetaan aina. Vaihtoehtona on määrittää merkille useampi kuin yksi päättelysääntö, jolloin kullekin säännölle annetaan suoritustodennäköisyys . Esimerkiksi esimerkin 2 kieliopissa voimme korvata uudelleenkirjoitussäännön "0":lla

0 → 1[0]0

todennäköisyysperiaatteella

0 (0,5) → 1[0]0 0 (0,5) → 0

Näillä päättelysäännöillä, kun "0" kohdataan syötemerkkijonossa, on 50 % todennäköisyys, että käyttäytyminen on sama kuin ennen, ja 50 % mahdollisuus, että mikään ei muutu. Jos stokastista kielioppia käytetään evoluution yhteydessä , on suositeltavaa, että satunnaisuuden generaattori sisällytetään genotyyppiin , jotta kuvion stokastiset ominaisuudet pysyvät vakioina sukupolvien välillä.

Tilanneherkät kieliopit

Tilannekohtainen päättelysääntö ei tarkastele ainoastaan ​​muokkaamiaan merkkejä, vaan myös niitä edeltäviä ja seuraavia merkkejä. Esimerkiksi päättelysääntö:

b <a > c → aa

muuntaa "a":n "aa":ksi, mutta vain jos "a" sattuu olemaan syötemerkkijonon "b" ja "c" välillä:

…bac…

Kuten satunnaisessa päättelyssä, on useita sääntöjä merkkien käsittelyyn eri yhteyksissä. Jos määritetylle kontekstille ei löydy generointisääntöä, oletetaan identiteettimuunnos eikä symbolia muuteta. Jos samassa kielioppissa on sekä kontekstista riippumattomia että riippumattomia päättelysääntöjä, kontekstiriippuvainen päättelysääntö on etusijalla (jos sitä voidaan soveltaa).

Parametriset kieliopit

Parametrisessa kielioppissa jokaisella aakkosten merkillä on merkkiin liittyvä parametriluettelo. Symbolia yhdessä parametrien kanssa kutsutaan moduuliksi ja merkkijonoa parametrisessa kielioppissa moduulien sarja. Esimerkki olisi seuraava rivi:

a(0,1)[b(0,0)]a(1,2)

Parametreja voidaan käyttää sekä piirustusfunktiossa että päättelysäännöissä. Päättelysäännöt voivat käyttää parametreja kahdella tavalla. Ensimmäisessä tapauksessa parametria käytetään ehdollisessa lausekkeessa, joka määrittää, tuleeko päättelysääntöä soveltaa. Toisessa tapauksessa päättelysääntö voi korvata todelliset parametrit. Esimerkiksi päättelysääntö:

a(x,y) : x == 0 → a(1, y+1)b(2,3)

Moduuli a(x,y) käy läpi muunnoksen tämän säännön mukaisesti, jos x=0 pätee. Esimerkiksi a(0,2) käy läpi muunnoksen, mutta a(1,2) ei.

Päättelysäännön oikealla puolella (seuraajassa) voidaan muuttaa sekä parametreja että kokonaisia ​​moduuleja. Yllä olevassa esimerkissä moduuli b(x,y) lisätään merkkijonoon alkuparametreilla (2,3). Jo olemassa olevan moduulin parametrit muunnetaan. Yllä kuvattujen sääntöjen mukaisesti

a(0,2)

Tulee

a(1,3)b(2,3)

koska moduulin a(x,y) parametri "x" muunnetaan eksplisiittisesti arvoksi "1" ja parametria "y" kasvatetaan yhdellä.

Parametriset kieliopit mahdollistavat segmentin pituuden ja haaran kulman määrittämisen kielioppiin, ei kilpikonnagrafiikan tulkintamenetelmiin. Jos moduulin parametriksi asetetaan myös ikä, sääntöjä voidaan muuttaa kasvisegmentin iän mukaan, jolloin voidaan luoda animaatio puun koko elinkaaresta.

Muut L-järjestelmien luokat

  • D0L-järjestelmät = deterministiset yhteydettömät järjestelmät (katso edellä)
  • Propagatiiviset L-järjestelmät ("Propagatiiviset L-järjestelmät", "pL-järjestelmät") ovat järjestelmiä, joissa vähintään yhden säännön oikealla puolella (ulostulossa) on vähintään kaksi kirjainta. Ei-jalostusjärjestelmissä on vain yksi symboli oikealla puolella. Sanan pituus ei tässä tapauksessa muutu [3] .
  • Kiinnitetyt L-järjestelmät (katso esimerkki 2)
  • 0L-järjestelmät, 1L-järjestelmät, 2L-järjestelmät (IL-järjestelmät, tunnetaan myös nimellä (k,l)-järjestelmät) [4] .
  • Taulukkomaiset L-järjestelmät ("T0L-järjestelmät") ovat järjestelmiä, jotka toimivat useiden sääntöjen kanssa. Sääntöjoukon valitsemiseen käytetään ulkoista ohjausmekanismia. Rosenberg otti käyttöön ja muodosti taulukkomaiset L-järjestelmät vuonna 1975 mallintaakseen ympäristön vaikutusta kasvien kasvuun [5] .

Avoimet numerot

L-järjestelmien tutkimukseen liittyy monia avoimia ongelmia. Esimerkiksi:

  • Kuvaus kaikista deterministisista kontekstittomista paikallisesti katentiivisista L-järjestelmistä. (Täydellinen ratkaisu tunnetaan vain kolmen muuttujan tapauksessa) [6] .
  • Kun on annettu rakenne, etsi L-järjestelmä, joka voi toistaa tämän rakenteen.
  • Kun annetaan kaksi pL-järjestelmää ja interpolointifunktio, ovatko saadut piirustukset yhteneviä [4] ?
  • Jos pL-järjestelmä ja tulkintafunktio on annettu, suljetaanko tuloksena oleva käyrä? Onko se leikkaava vai puumainen? Piirretäänkö jotkin janat useammin kuin kerran? [4] ?

Vastaukset näihin kysymyksiin ovat mielenkiintoisia paitsi teoreettisesta näkökulmasta, ne ovat hyödyllisiä myös pL-järjestelmien rakentamisessa tietyillä ominaisuuksilla varustettujen piirustusten luomiseen [4] .

L-järjestelmien tyypit

L-järjestelmät todellisella akselilla R :

Tunnetut L-järjestelmät koneessa R2 :

Katso myös

Muistiinpanot

  1. ↑ Rozenberg, Salomaa, 1980 .
  2. ↑ Manousakis, 2006 , s. 26.
  3. ↑ Manousakis, 2006 , s. 28.
  4. ↑ 1 2 3 4 Prusinkiewicz, 1986 , s. 252.
  5. ↑ Manousakis, 2006 , s. 29.
  6. ↑ Kari, Rozenberg, Salomaa, 1997 , s. 262.

Kirjallisuus

  • Grzegorz Rozenberg, Arto Salomaa. L-järjestelmien matemaattinen teoria. - New York: Academic Press, 1980. - ISBN 0-12-597140-0 .
  • Przemysław Prusinkiewicz, Aristid Lindenmayer . Kasvien algoritminen kauneus. - Springer, 2004.
  • Grzegorz Rozenberg, Arto Salomaa. Lindenmayer Systems: Vaikutukset teoreettiseen tietojenkäsittelytieteeseen, tietokonegrafiikkaan ja kehitysbiologiaan. - Springer-Verlag, 1992. - ISBN 978-3-540-55320-5 .
  • D.S. Ebert, F.K. Musgrave, D. Peachey, K. Perlin. Teksturointi ja mallintaminen: menettelyllinen lähestymistapa. - Academic Press, 1994. - ISBN 0-12-228730-4 .
  • Burry, Jane, Burry Mark. Uusi arkkitehtuurin matematiikka. - New York: Thames ja Hudson, 2010.
  • Aristid Lindenmayer. Matemaattiset mallit solujen vuorovaikutukseen kehityksessä // J. Theoret. Biologia. - 1968. - Numero. 18 . - S. 280-315 .
  • P. prusinkiewicz. Proceedings of Graphics Interface '86 / Vision Interface '86. - 1986. - S. 247-253 ..
  • Muodollisten kielten käsikirja / G.Rozenberg, A.Salomaa. - Springer, 1997. - V. 1 (Sana, kieli, kielioppi). - S. 253-328. - ISBN 978-3-642-63863-3 .
  • Stelios Manousakis. Musical L-Systems. - Haag: Kuninkaallinen konservatorio, 2006. - (Pro gradu - Sonology).

Linkit