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&ndash;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

:

tuottaa seuraavat merkkijonot n iteraatiolla:

:

### 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 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 http://algorithmicbotany.org/papers/#abop.