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 $V$ aakkosto. Merkitään aakkoston kaikkien merkkijonojen joukkoa $V^*$ ja aakkoston kaikkien epätyhjien merkkijonojen joukkoa $V^+$.

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

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

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

Olkoon $\mu = a_1 \ldots a_m$ mielivaltainen aakkoston $V$ merkkijono. Merkkijono $\nu = \chi_1 \ldots \chi_m$, $\chi_i \in V^*$, voidaan johtaa suoraan merkkijonosta $\mu$ (merkitään $\mu \Rightarrow \nu$) joss $a_i \rightarrow \chi_i$ kaikille $i = 1, \ldots, m$. OL-systeemi $G$ tuottaa merkkijonon $\nu$ jos on olemassa merkkijonot $\mu_0, \mu_1, \ldots, \mu_n$ joille pätee $\mu_0 = \omega$, $\mu_n = \nu$ ja $\mu_0 \Rightarrow \mu_1 \Rightarrow \ldots \Rightarrow \mu_n$.

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

Esimerkki

DOL-systeemi

$V$	:	A B
$\omega$	:	B
$p_1$	:	A $\rightarrow$ AB
$p_2$	:	B $\rightarrow$ A

tuottaa seuraavat merkkijonot $n$ iteraatiolla:

$n = 0$	:	B
$n = 1$	:	A
$n = 2$	:	AB
$n = 3$	:	ABA
$n = 4$	:	ABAAB
$n = 5$	:	ABAABABA
$n = 6$	:	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 $\pi : P \rightarrow (0,1]$, joka yhdistää jokaiseen sääntöön todennäköisyyden, jolla sääntöä käytetään merkkijonoja johtaessa. Jokaiselle $a \in V$ niiden sääntöjen, joissa $a$ 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 yhteyherkkiä 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

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