0.

Úvod

1.	Lindenmayerovy systémy

1.1.	Biologická motivace

1.2.	Úvod do Lindenmayerových systémů

1.3.	Gramatika Lindenmayerových systémů

1.4.	Základní členění Lindenmayerových systémů

2.	0L systémy

3.	Růstové funkce

4.	Dospělé jazyky

5.	E0L systémy

6.	T0L systémy

7.	IL systémy

8.	Regenerace v IL systémech

9.	Vztah L systémů a gramatik Chomského typu

10.	Geometrická interpretace řetězců generovaných Lindenmayerovými systémy

11.	Aplikace Lindenmayerových systémů

12.	Programy pro grafickou reprezentaci Lindenmayerových systémů

13.	Inference Lindenmayerových systémů

14.	Dokumentace k výukovému programu

14.1.

Provozní konfigurace

14.2.

Implementace

14.3.

Uživatelská dokumentace

15.

Závěr

"1. LINDENMAYEROVY SYSTÉMY
1.1. BIOLOGICKÁ MOTIVACE
Jazyk je základním nástrojem lidské abstrakce - prostředkem pro redukci rozmanitosti jevu složitého vnímaného světa do uchopitelného množství kategorií. Cílem teorie formálních jazyků je popsat strukturu jazyka prostředky algebry, popřípadě vytvořit specializované nástroje pro tento účel. Základním východiskem teorie formálních jazyků byla struktura přirozeného jazyka, brzy byla ale vytvořena vlastní struktura formálních jazyků s exaktní syntaxí a sémantikou, vhodná pro komunikaci se stroji. Další aplikace teorie formálních jazyků se postupně uplatnily v oblastech:
- modelování biologické reality (procesu organického růstu) a umělého života (Artifical Life),
- počítačového zpracování obrazu (tvorba, analýza),
- modelování možností buněčných a molekulárních výpočtů (H-systémy - modely DNA počítačů, P-systémy - modely membránových výpočtů),
- popisu distribuovaných výpočetních i reálných systémů (gramatické systémy)
- a dalších.
Původní přepisování řetězců symbolů na jiné řetězce pomocí generativních pravidel přestalo pro tyto nové aplikace dostačovat. Postupně byla teorie formálních jazyků obohacována o prostředky jako:
- teorie grafů (grafové gramatiky),
- topologická pravidla (2D a 3D gramatiky pro popis obrazu),
- regulace generování pomocí kontextu (kontextuální gramatiky, regulované gramatiky),
- synchronizaci, paralelizmus (Lindenmayerovy systémy),
- distribuci komponent, hierarchie, protokoly (gramatické systémy).
Výzkum gramatických konstrukcí s výše uvedenými vlastnostmi je zaměřen jednak na aplikace, ovšem jeho výsledkem jsou též teoretické poznatky obohacující teorii formálních jazyků, bohatá hierarchie tříd jazyků se zajímavými vlastnostmi, vztahy k jiným disciplínám (lingvistika, teorie čísel, apod.).
Jednou z prvních koncepcí teorie formálních jazyků přesahující studium přirozených a počítačových jazyků byly Lindenmayerovy systémy, zkráceně L-systémy.
1.2. ÚVOD DO LINDENMAYEROVÝCH SYSTÉMŮ
V přírodě se vyskytuje mnoho přírodních objektů, které mají tu vlastnost, že celek a jeho části jsou si podobné. To platí například o stromu a jeho větvi nebo o skále a úlomku. A jelikož dochází v posledních letech k velkému rozvoji v oblasti generování syntetických scén, setkáváme se při tvorbě tvaru okolní krajiny nebo rostlin s velkou složitostí těchto přírodních struktur, jejichž popis by byl velmi náročný. Členitost těchto objektů způsobuje informatikům problém, jak je nejlépe uložit v paměti počítače. A protože jejich reprezentace, například vektorovou grafikou, by byla značně nehospodárná, využívá se jisté pravidelnosti těchto objektů a hledají se různé matematické objekty, kterými by bylo možné je nejlépe popsat.
Lindenmayerovy systémy zavedl Aristid Lindenmayer jako modifikaci formální gramatiky pro účely modelování vývoje jednoduchých vícebuněčných organizmů. Svoji teorii předvedl poprvé v roce 1968.
Tyto systémy je možné považovat za speciální případ celulárních automatů vzhledem k tomu, že stav prvku v následujícím kroku je odvozený od aktuálních stavů okolních prvků. Pravidla jsou v zásadě rekurzivní, což zaručuje soběpodobnost, charakteristickou vlastnost fraktálů. Ukázalo se, že i velmi jednoduchá soustava pravidel byla schopná simulovat proces růstu, resp. morfologii složitých struktur.
Vlastní L-systémy generují jen řetězce znaků. Bylo potřebné je nějakým způsobem interpretovat jako pravidla pro růst, větvení, tvorby pupenců, listů a květů.
Lindenmayerovi žáci, Ben Hesper a Pauline Hogeweg, začali v roce 1970 zkoumat, zda jsou L-systémy schopné generovat také obrazy rostlin. Řetězec, reprezentující morfologii rostliny, nazvali morfém. Své poznatky s generováním 3 584 umělých rostlin publikovali (Hogeweg a Hesper, 1974).
Lindenmayer ze začátku považoval tyto experimenty za nedůstojné a svoje studenty od nich odrazoval. Obrázky používal jen na svých novoročenkách.
Matematik Alvy Ray Smith byl naopak fascinovaný touto schopností L-systémů. Měl k celulárním automatům blízký vztah, ve své disertaci podal důkaz možnosti sestrojit univerzální počítač v 1-D CA. Stal se jedním z nejslavnějších představitelů počítačového umění. Ve svých dílech kombinoval rostliny generované L-systémy (používal pro ně termín graftály) s prvkami, které vytvářel pomocí klasických fraktálů.
V polovině 80-tých let Lindenmayer připustil, že generování virtuálních rostlin pomocí L-systémů pomáhá odhalit zákonitosti morfogenézy. Jeho nový spolupracovník Przemyslaw Prusinkiewicz začal detailně studovat pravidla, kterými se řídí procesy růstu, větvení, tvorby pupenců, listů a květů. Ukázalo se, že pomocí L-systémů je možné začít od jediné buňky, z které postupně vyrůstá vícebuněčná embryonální struktura a nakonec celá entita. Přesvědčivým příkladem je porovnání morfogenézy gametofytu (první vývojová fáze nižších rostlin), který vytvořil Martin de Boer pomocí L-systémů s mikroskopickými snímkami prvních vývojových kroků zárodku kapradí Microsorium lingueforme.
Pro účely modelování vývoje rostlin byly nalezeny takové metody interpretace řetězce, které umožňují vytvářet i realistické obrazy modelovaných rostlin. Při modelování rostlin pro účely počítačové grafiky se ve velké míře využívají biologické znalosti o jejich vývoji a mechanizmech, které ho řídí. L-systémy a jejich grafická interpretace dávají na druhé straně velké možnosti biologům. Umožňují jim sledovat vývoj rostliny za různých podmínek, testovat teorie o vnitřních mechanizmech řídících vývoj rostliny i o působení vnějšího prostředí. Nabízejí prostředky pro zjišťování parametrů těchto mechanizmů, například rychlosti šíření signálů v rostlině apod.
1.3. GRAMATIKA LINDENMAYEROVÝCH SYSTÉMŮ
Gramatiku používanou v L-systémech lze definovat jako:
,
kde jsou neterminály,
jsou terminály,
jsou přepisovací pravidla,
je startovací fráze, nazývaná axiom."

Práce obsahuje obrázky a schémata. Čistý text je cca 48 stran.