L-systeemi

L-systeemi, tai Lindenmayer-systeemi, on matemaattinen malli, jonka avulla on mallinnettu ja simuloitu kasvien rakennetta ja kasvua. Niiden avulla voidaan mallintaa myös muiden eliöiden rakennetta sekä esimerkiksi joitain fraktaaleja. Unkarilainen teoreettinen biologi ja kasvitieteilijä Aristid Lindenmayer (1925–1989) kehitti L-systeemit vuonna 1968.

Erilaisia L-systeemejä
L-systeemi on formaalien kielioppien tapaan uudelleenkirjoitukseen perustuva tapa luoda tietyn alkuarvon ja sääntöjen perusteella kielen merkkijonoja. Merkittävin ero Chomskyn kielioppeihin on se, että L-systeemeissä annetun merkkijonon seuraaja muodostetaan korvaamalla sääntöjen perusteella merkkijonon jokainen merkki, kun taas Chomskyn kieliopeissa korvataan yksi merkki kerrallaan.

Yhteysriippumaton L-systeemi
Olkoon  aakkosto. Merkitään aakkoston kaikkien merkkijonojen joukkoa  ja aakkoston kaikkien epätyhjien merkkijonojen joukkoa .

Yhteysriippumaton L-systeemi (OL-systeemi) on kolmikko , missä
  on aakkosto,
  on alkuperäinen merkkijono (aksiooma) ja
  on äärellinen joukko sääntöjä.

Sääntö  kirjoitetaan muodossa . Merkkiä  kutsutaan edeltäjäksi ja merkkijonoa  seuraajaksi. Jokaiselle merkille  on olemassa seuraaja  s.e. . Jos jonkin aakkosen sääntöä ei ole erikseen mainittu, oletetaan säännöksi .

Olkoon  mielivaltainen aakkoston  merkkijono. Merkkijono , , voidaan johtaa suoraan merkkijonosta  (merkitään ) joss  kaikille . OL-systeemi  tuottaa merkkijonon  jos on olemassa merkkijonot  joille pätee ,  ja .

Yhteysriippumaton L-systeemi on deterministinen (DOL-systeemi), jos jokaiselle aakkoselle  on :ssä tarkalleen yksi sääntö, jossa  on edeltäjä.

Esimerkki
DOL-systeemi

{|
|-
| ||: || A B
|-
| ||: || B
|-
| ||: || A  AB
|-
| ||: || B  A
|}

tuottaa seuraavat merkkijonot  iteraatiolla:

{|
|-
| ||: || B
|-
| ||: || A
|-
| ||: || AB
|-
| ||: || ABA
|-
| ||: || ABAAB
|-
| ||: || ABAABABA
|-
| ||: || ABAABABAABAAB
|}

Stokastinen yhteysriippumaton L-systeemi
Eräs epädeterministinen L-systeemi on stokastinen yhteysriippumaton L-systeemi. Se on muuten kuin OL-systeemi, mutta sisältää lisäksi funktion , joka yhdistää jokaiseen sääntöön todennäköisyyden, jolla sääntöä käytetään merkkijonoja johtaessa. Jokaiselle  niiden sääntöjen, joissa  on edeltäjä, todennäköisyyksien summa on 1.

Yhteysherkkä L-systeemi
OL-systeemit ovat yhteysriippumattomia (context-free), koska edeltäjämerkin yhteys (tai konteksti), eli sen viereiset merkit alkuperäisessä merkkijonossa, eivät vaikuta sääntöjen soveltamiseen. Yhteysherkissä L-systeemeissä sääntöjen soveltaminen riippuu myös merkin viereisistä merkeistä. L-systeemeille on kehitetty monenlaisia yhteysherkkiä laajennoksia, esimerkiksi 1L- ja 2L-systeemit. 1L-systemeissä edeltäjän lisäksi yhden merkin edeltäjän jommaltakummalta puolelta pitää täsmätä sääntöön, jotta sääntöä voidaan soveltaa. 2L-systeemeissä taas edeltäjän lisäksi yhden merkin edeltäjän kummaltakin puolelta pitää täsmätä sääntöön.

Lähteet
  Saatavilla myös Calgaryn yliopiston Biological Modeling and Visualization research groupin Internet-sivuilta PDF-muodossa .

Luokka:Biologia
Luokka:Formaalit kielet

Luokka:Sovellettu matematiikka