причиною їх широкого застосування в комп'ютерній графіці для побудови фрактальних дерев і рослин. Розглянуті в цій роботі L-системи обмежуються випадком детермінованих L-систем та графікою на площині.
Для графічної реалізації L-систем в якості підсистеми виводу використовується так звана Тертл -графіка (turtle - черепаха). При цьому точка (черепашка) рухається по екрану дискретними кроками, як правило прокреслюючи свій слід, але при необхідності може переміщатися без малювання. У нашому розпорядженні є три параметри ( x, y, a) , де ( x, y) --- координати черепашки, a --- напрямок, в якому вона дивиться. Черепашка навчена інтерпретувати і виконувати послідовність команд, що задаються кодовим словом, літери якого читаються зліва направо. Кодове слово являє собою результат праці L-системи і може включати наступні літери:
F --- переміститися вперед на один крок, прорисовуючі слід.
b --- переміститися вперед на один крок, НЕ прорисовуючі слід.
[ --- Відкрити гілку (докладніше див нижче)
] --- Закрити гілку (докладніше див нижче)
+ --- Збільшити кут a на величину q
- --- Зменшити кут a на величину q
Розмір кроку і величина збільшення по куту q задаються заздалегідь і залишаються незмінними для всіх переміщень черепашки. Якщо початкове напрямок руху а (кут, що відраховується від позитивного напрямку осі Х) не зазначено, то вважаємо а рівним нулю.
Кілька прикладів ілюструють застосування команд розгалуження (позначаються], [) і допоміжних змінних (позначаються X, Y, тощо). Команди розгалуження використовуються для побудови дерев рослин, а допоміжні змінні помітно полегшують побудову деяких L-систем.
Формально, детермінована L-система складається з алфавіту , слова ініціалізації, званого аксіомою або ініціатором , і набору породжують правил , що вказують, як слід перетворювати слово при переході від рівня до рівня (від ітерації до ітерації). Приміром, можна замінювати букву F за допомогою породжує правила newf = F-F + + FF, що відповідає L-системі для сніжинки Коха, розглянутої нижче. Символи +, -,], [not оновлюються, а просто залишаються на тих місцях, де вони зустрілися. Оновлення літер у даному слові передбачається одночасним, тобто букви слова одного рівня оновлюються раніше будь-який літери наступного рівня.
L-система, відповідна снежинке Коха (рис. 2.2.1), задається наступним чином:
p = p /3
Аксіома: F + + F + + F
Породжує правило: newf = F-F + + F-F
Графічне подання аксіоми F + + F + + F --- рівносторонній трикутник. Черепашка робить один крок вперед, потім кут а збільшується на 2p/3 і черепашка робить ще один крок.
На першому кроці кожна буква F ...