L-systém

L-systém alebo Lindenmayerov systém je druh formálnej gramatiky známy najmä vďaka svojmu použitiu pri modelovaní vývinu rastlín, ako aj ďalším biologickým aplikáciám. L-systémy môžu byť použité aj na generovanie niektorých typov fraktálov (napr. Kochova vločka). Sú pomenované podľa maďarského teoretického biológa a botanika Aristida Lindenmayera (toho času pôsobiaceho na univerzite v Utrechte), ktorý s týmto konceptom prišiel v roku 1968.

Obrázky rastlín generované použitím 3D L-systémov.

Formálne sa L-systém definuje ako trojica $G=(\Sigma ,R,A)$, kde $\Sigma$ je abeceda, t. j. konečná neprázdna množina znakov, $R$ je množina prepisovacích pravidiel a $A\in \Sigma ^{\ast }$ je tzv. axióma - konečné slovo nad abecedou $\Sigma$, v ktorom odvodenie začína.

L-systémy sú podobné frázovým gramatikám - abeceda aj množina prepisovacích pravidiel sa vyskytujú aj v definícii frázovej gramatiky, axióma je analógiou tzv. počiatočného neterminálu. Najväčším rozdielom však je, že sa nerozlišujú množiny terminálnych a neterminálnych symbolov - odvodenie končí, pokiaľ sa nedá použiť žiadne z prepisovacích pravidiel. Jestvujú však definície L-systémov, ktoré pripúšťajú aj analógiu terminálnych symbolov - tzv. konštanty, ktoré sa nemôžu vyskytovať na ľavej strane žiadneho odvodzovacieho pravidla.