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.

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.

Olkoon ${\displaystyle V}$ aakkosto. Merkitään aakkoston kaikkien merkkijonojen joukkoa ${\displaystyle V^{*}}$ ja aakkoston kaikkien epätyhjien merkkijonojen joukkoa ${\displaystyle V^{+}}$.

Yhteysriippumaton L-systeemi (OL-systeemi) on kolmikko ${\displaystyle G=\left(V,\omega ,P\right)}$, missä

• ${\displaystyle V}$ on aakkosto,
• ${\displaystyle \omega \in V^{+}}$ on alkuperäinen merkkijono (aksiooma) ja
• ${\displaystyle P\subset V\times V^{*}}$ on äärellinen joukko sääntöjä.

Sääntö ${\displaystyle (a,\chi )\in P}$ kirjoitetaan muodossa ${\displaystyle a\rightarrow \chi }$. Merkkiä ${\displaystyle a}$ kutsutaan edeltäjäksi ja merkkijonoa ${\displaystyle \chi }$ seuraajaksi. Jokaiselle merkille ${\displaystyle a\in V}$ on olemassa seuraaja ${\displaystyle \chi \in V^{*}}$ s.e. ${\displaystyle a\rightarrow \chi }$. Jos jonkin aakkosen sääntöä ei ole erikseen mainittu, oletetaan säännöksi ${\displaystyle a\rightarrow a}$.

Olkoon ${\displaystyle \mu =a_{1}\ldots a_{m}}$ mielivaltainen aakkoston ${\displaystyle V}$ merkkijono. Merkkijono ${\displaystyle \nu =\chi _{1}\ldots \chi _{m}}$, ${\displaystyle \chi _{i}\in V^{*}}$, voidaan johtaa suoraan merkkijonosta ${\displaystyle \mu }$ (merkitään ${\displaystyle \mu \Rightarrow \nu }$) joss ${\displaystyle a_{i}\rightarrow \chi _{i}}$ kaikille ${\displaystyle i=1,\ldots ,m}$. OL-systeemi ${\displaystyle G}$ tuottaa merkkijonon ${\displaystyle \nu }$ jos on olemassa merkkijonot ${\displaystyle \mu _{0},\mu _{1},\ldots ,\mu _{n}}$ joille pätee ${\displaystyle \mu _{0}=\omega }$, ${\displaystyle \mu _{n}=\nu }$ ja ${\displaystyle \mu _{0}\Rightarrow \mu _{1}\Rightarrow \ldots \Rightarrow \mu _{n}}$.

Yhteysriippumaton L-systeemi on deterministinen (DOL-systeemi), jos jokaiselle aakkoselle ${\displaystyle a\in V}$ on ${\displaystyle P}$:ssä tarkalleen yksi sääntö, jossa ${\displaystyle a}$ on edeltäjä.

DOL-systeemi

${\displaystyle V}$	:	A B
${\displaystyle \omega }$	:	B
${\displaystyle p_{1}}$	:	A ${\displaystyle \rightarrow }$ AB
${\displaystyle p_{2}}$	:	B ${\displaystyle \rightarrow }$ A

tuottaa seuraavat merkkijonot ${\displaystyle n}$ iteraatiolla:

${\displaystyle n=0}$	:	B
${\displaystyle n=1}$	:	A
${\displaystyle n=2}$	:	AB
${\displaystyle n=3}$	:	ABA
${\displaystyle n=4}$	:	ABAAB
${\displaystyle n=5}$	:	ABAABABA
${\displaystyle n=6}$	:	ABAABABAABAAB

Eräs epädeterministinen L-systeemi on stokastinen yhteysriippumaton L-systeemi. Se on muuten kuin OL-systeemi, mutta sisältää lisäksi funktion ${\displaystyle \pi :P\rightarrow (0,1]}$, joka yhdistää jokaiseen sääntöön todennäköisyyden, jolla sääntöä käytetään merkkijonoja johtaessa. Jokaiselle ${\displaystyle a\in V}$ niiden sääntöjen, joissa ${\displaystyle a}$ on edeltäjä, todennäköisyyksien summa on 1.

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.

• P. Prusinkiewicz & A. Lindenmayer: The Algorithmic Beauty of Plants. Springer-Verlag, 1990. Saatavilla myös Calgaryn yliopiston Biological Modeling and Visualization research groupin Internet-sivuilta PDF-muodossa [1].