L-сістэма

L-сістэма, сістэма Ліндэнмаера — тып фармальнай граматыкі, які быў распрацаваны для мадэлявання росту раслін венгерскім біёлагам Арыстыдам Ліндэнмаерам у 1968 годзе. L-сістэма складаецца з алфавіта сімвалаў, якія патрэбны для стварэння радкоў, набору правіл, па якім кожны сімвал замяняецца на адпаведны радок, пачатковага радка («аксіёмы»), з якога пачынаецца пабудова, і механізма, які пераўтварае атрыманы радок у геаметрычныя структуры.

Структура L-сістэмы

Правіла L-сістэмы маюць рэкурсіўную прыроду, таму іх лёгка выкарыстоўваць для апісвання фракталападобных форм.

L-сістэмы вядомыя зараз як параметрычныя L-сістэмы, якія азначаюцца як картэж

G = (V, ω, P),

дзе

V (алфавіт) — гэта мноства сімвалаў, якія змяшчаюць як элементы, якія могуць быць замененыя (пераменныя), так і элементы, якія не могуць быць замененыя (канстанты)
ω (старт, аксіёма або ініцыятар) — гэта радок сімвалаў з V, якія вызначаюць пачатковы стан сістэмы
P — гэта канечнае мноства правіл, якое вызначае, якім чынам пераменныя могуць быць замененыя камбінацыямі канстант і іншых пераменных. Правілы запісваюцца ў выглядзе a → S, дзе a — гэта сімвал (папярэднік), які будзе заменены на радок сімвалаў S (пераемнік). Калі папярэднік a не сустракаецца ў левай частцы ніводнага з правілаў маецца на ўвазе, што a → a. Такія сімвалы часта называюць канстантамі.

Ітэратыўнае развіццё L-сістэмы

Правілы граматыкі L-сістэмы прымяняюцца ітэратыўна, пачынаючы з аксіёмы (пачатковага стану), якая з’яўляецца нулявой ітэрацыяй. Усе наступныя ітэрацыі ствараюцца шляхам паралельнага прымянення правілаў перазапісу да вынікаў папярэдніх ітэрацый.

Паралельнае прымяненне — гэта замена ўсіх сімвалаў «адразу». Паралельны перазапіс можа таксама выконвацца паслядоўна, а менавіта шляхам паслядоўнага перазапісу сімвалаў злева направа, але вынік захоўваецца ў іншым месцы. Гэта гарантуе, што сімвалы, створаныя шляхам перазапісу, не будуць перазапісаны другі раз у дадзенай ітэрацыі.

Прыклады L-сістэм

Крывая Коха

Пераменная : F

Канстанты : + −

Аксіёма : F

Правілы : (F → F+F−F−F+F)

Тут F азначае «малюем адрэзак», + азначае «павярнуць налева на 90°», а − азначае «павярнуць направа на 90°»

n = 0:

F

n = 1:

F+F−F−F+F

n = 2:

F+F−F−F+F + F+F−F−F+F − F+F−F−F+F − F+F−F−F+F + F+F−F−F+F

n = 3:

F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F +

F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F −

F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F +

F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F

Фрактальная расліна

Пераменная : X F

Канстанты : + − [ ]

Аксіёма : -X

Правілы : (X → F+[[X]-X]-F[-FX]+X), (F → FF)

Тут F азначае «малюем адрэзак», + азначае «павярнуць налева на 25°», − азначае «павярнуць направа на 25°», а X не адпавядае ніякім дзеянням. На «[» значэння пазіцыі і вугла захоўваюцца ў стэк, а калі сустракаецца «]» бягучыя пазіцыя і вугал скідваюцца і са стэка бяруцца старыя. Пасля кожнага «[» патрэбна ставіць «]», каб не выклікаць перапаўненне стэка.

Фрактальная расліна пасля шостай ітэрацыі

Гл. таксама

Літаратура

Przemysław Prusinkiewicz, Aristid Lindenmayer. The Algorithmic Beauty of Plants. — Springer, 2004.

Спасылкі

Algorithmic Botany at the University of Calgary