L-systém

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie
Obrázky rastlín generované použitím 3D L-systémov.

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.

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.