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 +
 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 не адпавядае ніякім дзеянням. На «[» значэння пазіцыі і вугла захоўваюцца ў стэк, а калі сустракаецца «]» бягучыя пазіцыя і вугал скідваюцца і са стэка бяруцца старыя. Пасля кожнага «[» патрэбна ставіць «]», каб не выклікаць перапаўненне стэка.

alt=|leftalt=

 Гл. таксама 

 Фрактал
 Мадэляванне

 Літаратура 


 Спасылкі 
 Algorithmic Botany at the University of Calgary

Катэгорыя:Фракталы