L-системы: грамматика природы

Биолог, водоросли и язык роста

В 1968 году венгерский биолог Аристид Линденмайер работал в Утрехтском университете над, казалось бы, скучной задачей: он изучал, как делятся клетки нитчатых водорослей Anabaena catenula. Водоросль росла цепочкой клеток, каждая из которых в определённый момент делилась надвое — но не случайно. Клетки двух типов, зрелые и незрелые, делились по разным правилам, и из этого простого факта рождался сложный, повторяющийся паттерн.

Линденмайер был биологом с математической жилкой. Ему нужен был строгий формальный язык, чтобы записывать и предсказывать такие паттерны. Он придумал систему, которую сегодня называют его именем — L-система (Lindenmayer system). Идея была предельно простой: взять строку символов, применить к ней правила замены — и повторять. Итерация за итерацией. Каждый символ порождает новую подстроку, та — ещё одну, и так до любой желаемой глубины.

Линденмайер не думал о фракталах — этого слова ещё не существовало (Мандельброт введёт его только в 1975 году). Он думал о росте клеток. Но обнаружил нечто гораздо большее: формальный язык, в котором закодировано самоподобие природы.

Как работает L-система

L-система состоит из трёх компонентов:

Алфавит — набор символов. Например, {F, +, -, [, ]}.

Аксиома — начальная строка, с которой всё начинается. Например, просто F.

Правила переписывания — набор замен вида «символ → строка». Например: F → F+F--F+F.

На каждом шаге (итерации) каждый символ строки одновременно заменяется по соответствующему правилу. Символы, для которых правила нет, остаются как есть.

Разберём пример шаг за шагом:

Аксиома: F
Правило: F → F+F--F+F
Итерация 0: F
Итерация 1: F+F--F+F
Итерация 2: F+F--F+F + F+F--F+F -- F+F--F+F + F+F--F+F

Итерация 2 уже содержит 28 символов F и 36 знаков поворота. После трёх итераций строка разрастается до сотен символов.

Но строка сама по себе ничего не рисует. Её нужно интерпретировать. Для этого используется черепашья графика (turtle graphics) — метод, пришедший из учебного языка программирования LOGO:

F — черепашка делает шаг вперёд, рисуя линию
+ — поворот влево на угол δ
- — поворот вправо на угол δ
[ — запомнить текущую позицию и направление (стек)
] — вернуться к последней сохранённой позиции (из стека)

Угол δ задаётся отдельно. Именно он определяет «характер» рисунка: при одних и тех же правилах переписывания разные углы дают кардинально разные формы.

Это и есть вся механика. Никаких уравнений, никакой геометрии — только строки и правила замены. И тем не менее из этого рождаются папоротники, снежинки, кривые, заполняющие плоскость.

Четыре L-системы

Четыре лица одной идеи

Растение: как трава знает, куда расти

Один из канонических примеров «Алгоритмической красоты растений» Прусинкевича и Линденмайера:

Аксиома:  X
Правила:  X → F+[[X]-X]-F[-FX]+X
          F → FF
Угол:     25°

Скобки [ и ] — ключевое нововведение для ботанических L-систем. Они реализуют стековую память черепашки: [ сохраняет текущее положение и направление, ] возвращает обратно. Так рисуются ветки: черепашка «уходит» по ветке до конца, затем мгновенно возвращается в точку ветвления и идёт по следующей.

Символ X — вспомогательный. Он не рисует линию, но управляет структурой: именно в нём «живёт» рекурсия роста.

Поменяйте угол δ — и та же грамматика породит другое растение:

δ = 15° → вытянутое, похожее на кипарис или ель
δ = 25° → раскидистое, похожее на траву или молодое дерево
δ = 35° → приземистое и широкое, как кактус или суккулент

Длина строки на итерации n растёт экспоненциально (правило F → FF удваивает все «стебли»), что соответствует биологической реальности: каждый узел ветвления порождает два новых побега.

Снежинка Коха: бесконечный берег конечного острова

Аксиома:  F--F--F
Правила:  F → F+F--F+F
Угол:     60°

Аксиома F--F--F — это равносторонний треугольник (три стороны, каждый разворот — 120°). Правило F → F+F--F+F заменяет каждую прямую на «шип» из четырёх сегментов.

Нильс Фабиан Хельге фон Кох описал эту кривую в 1904 году, ещё за 60 лет до L-систем. Он искал пример непрерывной функции, нигде не дифференцируемой — математического «монстра», существование которого противоречило интуиции XIX века. Снежинка Коха была именно таким монстром: гладкая на вид, но в каждой точке «изломанная» до бесконечности.

Два удивительных свойства снежинки Коха:

Периметр бесконечен. На каждой итерации длина контура умножается на 4/3. После n итераций периметр равен начальному умножить на (4/3)^n. При n → ∞ периметр → ∞.
Площадь конечна. Снежинка всегда вписывается в круг конечного радиуса. Точная площадь = 8/5 площади исходного треугольника.

Это и есть фрактальное противоречие: бесконечная граница, ограничивающая конечную площадь. Мандельброт назвал снежинку Коха «образцовым примером» фрактала в своей книге 1982 года.

Фрактальная размерность Хаусдорфа снежинки: d = log(4) / log(3) ≈ 1.26. Это не целое число, но это и не случайность — именно дробная размерность является определяющим признаком фракталов.

Кривая дракона: бумажное складывание

Аксиома:  FX
Правила:  X → X+YF+
          Y → -FX-Y
Угол:     90°

История этой кривой начинается физически, а не математически. Представьте: вы берёте длинную бумажную ленту и складываете её пополам — всегда в одну и ту же сторону. Потом снова пополам. И снова. После n сложений разверните ленту, расправляя каждый сгиб до прямого угла — вы получите кривую дракона n-й итерации.

Математически её исследовали Джон Хёртер и Брюс Бэнкс, популяризировал Мартин Гарднер в 1967 году в колонке «Математические игры» в Scientific American. Там же её назвали «кривой дракона» за характерную «хвостатую» форму.

Два фундаментальных свойства кривой дракона:

Она никогда не самопересекается — это было строго доказано. Сколько бы ни было итераций, линия не пройдёт дважды через одну точку.
При 12 итерациях длина кривой составляет 4096 сегментов (2^12), и она уже настолько «закручена», что почти заполняет ограниченную область плоскости.

Четыре копии кривой дракона, повёрнутые на 0°, 90°, 180° и 270°, идеально складываются в квадрат — без пробелов и перекрытий. Это свойство самоподобия высшего порядка.

Кривая Гильберта: карта в одну линию

Аксиома:  A
Правила:  A → +BF-AFA-FB+
          B → -AF+BFB+FA-
Угол:     90°

В 1891 году Давид Гильберт поставил и решил задачу, казавшуюся абсурдной: существует ли непрерывная кривая, которая проходит через каждую точку квадрата? Джузеппе Пеано годом ранее доказал, что такие кривые теоретически возможны, но его пример был сложен для восприятия. Гильберт построил элегантную конструкцию: на каждой итерации каждый отрезок заменяется U-образным блоком из четырёх сегментов.

Предел этого процесса — кривая, которая «посещает» каждую точку единичного квадрата ровно один раз (точнее, при обходе с равномерной скоростью). Это называется пространство-заполняющая кривая (space-filling curve).

Практические применения кривой Гильберта сегодня:

Алгоритмы хранения данных. Z-кривые (Morton codes) и кривые Гильберта используются в базах данных для хранения двумерных геопространственных данных: соседние точки на плоскости оказываются близко расположены в линейной памяти.
Маршрутизация в сетях. Алгоритмы обхода матриц пикселей по кривой Гильберта уменьшают количество промахов кэша.
Сжатие изображений. Фракталы типа IFS используют родственную идею.

Итерация n кривой Гильберта содержит 4^n сегментов и покрывает сетку 2^n × 2^n. При n = 8 это 65536 сегментов и сетка 256 × 256 — уже достаточно для практических задач.

Природа говорит на этом языке

L-системы были придуманы для описания биологических паттернов — и они справляются с этим удивительно точно.

Лёгкие. Бронхиальное дерево человека хорошо описывается L-системой с 7 итерациями. Каждое ветвление происходит примерно под углом 35° и уменьшает диаметр трубки в соотношении 1:√2. Это не совпадение: такое ветвление минимизирует работу, затрачиваемую на перемещение воздуха, — природа оптимизировала конструкцию за сотни миллионов лет эволюции.

Кровеносные сосуды. Закон Мюррея (1926) описывает ветвление сосудов: сумма кубов радиусов дочерних ветвей равна кубу радиуса родительской. Это порождает фрактальную структуру с L-подобными правилами ветвления.

Подсолнух и числа Фибоначчи. Спирали семян подсолнуха следуют числам Фибоначчи (21, 34, 55, 89…), что является частным случаем L-системы с правилом, порождающим последовательность Фибоначчи. Угол между соседними семенами — золотое сечение в градусах (≈ 137.5°) — математически гарантирует максимальную плотность упаковки.

Папоротник Барнсли. Майкл Барнсли в 1988 году показал, что лист папоротника можно воспроизвести системой итерируемых функций (IFS) — математически родственной идеей. Четыре аффинных преобразования, применённые случайным образом миллион раз, рисуют идеальный лист. Этот «папоротник Барнсли» стал одним из символов фрактальной геометрии.

Кораллы и морские ветви. Ветвление колоний коралловых полипов, морских водорослей, нейронных дендритов — везде прослеживаются самоподобные паттерны, описываемые относительно простыми грамматиками роста.

Почему это «грамматика» в строгом смысле

В лингвистике формальная грамматика — это набор правил, порождающих язык. Ноам Хомский в 1956 году разработал иерархию грамматик: тип 3 (регулярные), тип 2 (контекстно-свободные), тип 1 (контекстно-зависимые), тип 0 (без ограничений).

L-системы — это разновидность порождающих грамматик, причём с одним ключевым отличием от традиционных: в обычных грамматиках на каждом шаге применяется одно правило, а в L-системах все применимые правила срабатывают одновременно (параллельная перезапись). Именно это делает L-системы подходящими для моделирования роста: все клетки делятся одновременно, а не по очереди.

Связь с лингвистикой не только формальная. Когда компилятор языка программирования разбирает выражение 2 + 3 * 4, он строит дерево разбора по правилам формальной грамматики языка. L-система, порождающая ветвящееся дерево, строит геометрическое дерево по правилам той же природы. Синтаксическое дерево программы и ботаническое дерево — математически родственные объекты.

Более того: контекстные L-системы (2L-системы) учитывают соседей символа при применении правил. Это прямой аналог контекстно-зависимых грамматик в иерархии Хомского и позволяет моделировать взаимодействия между клетками — передачу сигналов, гормональные градиенты, индукцию.

Бумажный эксперимент: снежинка Коха своими руками

Этот эксперимент не требует компьютера. Понадобятся: клетчатая бумага, карандаш, 30–40 минут.

Шаг 1. Запишите строки.

Аксиома: F

Применяем правило F → F+F--F+F три раза:

n=0: F (1 символ F)
n=1: F+F--F+F (4 символа F)
n=2: F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+F (16 символов F)
n=3: строка из 64 символов F

Посчитайте количество символов F на каждой итерации: 1 → 4 → 16 → 64. Множитель = 4. Число делений отрезка = 3.

Фрактальная размерность: d = log(4) / log(3) ≈ 1.2619

Шаг 2. Нарисуйте итерацию n=2.

Интерпретация: δ = 60°, шаг = 2 клетки.

F — нарисовать отрезок в текущем направлении (2 клетки)
+ — повернуть налево на 60°
- — повернуть направо на 60°

Начните с направления «вправо». Аккуратно следуйте каждому символу строки n=2. У вас получится одна сторона снежинки Коха (кривая Коха).

Шаг 3. Постройте три стороны.

Чтобы получить полную снежинку, нужно три таких кривых, соединённых под углом 120°. Аксиома F--F--F задаёт именно это: три стороны треугольника. Попробуйте нарисовать снежинку целиком для n=1 — это проще всего.

Шаг 4. Измерьте.

Измерьте суммарную длину нарисованных отрезков для n=1, n=2, n=3. Каждый раз длина умножается примерно на 4/3 ≈ 1.333. Убедитесь в этом на практике.

Технологии: от водорослей до видеоигр

L-системы вышли далеко за пределы биологии.

Процедурная генерация в играх. В No Man’s Sky алгоритмы на основе L-систем и родственных грамматик генерируют растительность на миллиардах планет — при этом каждое дерево выглядит органично и уникально. В Minecraft похожие алгоритмы порождают леса. Ключевое преимущество: огромное разнообразие при минимальном объёме кода.

Архитектурное проектирование. Параметрическая архитектура (Заха Хадид Архитектс, бюро Бига) использует алгоритмическое проектирование, в котором геометрические правила порождают сложные формы. Это не буквально L-системы, но математическая идея та же: простые правила → сложная структура.

Синтез музыки. Алгоритмическая музыка применяет L-системы для порождения мелодических и ритмических структур. Символы алфавита интерпретируются как ноты, длительности, динамика. Такие произведения сочетают математическую строгость с органичным, «природным» звучанием.

Сжатие изображений методом IFS. Системы итерируемых функций (Barnsley, 1988) используют самоподобие изображения: фрагменты изображения в разных масштабах похожи друг на друга. Вместо сохранения пикселей хранятся трансформации. Теоретически этот метод даёт огромные коэффициенты сжатия — задача поиска подходящих трансформаций оказалась вычислительно трудоёмкой, и метод не получил широкого распространения, но идея остаётся красивой.

Компьютерная графика и кино. Генерация реалистичных деревьев, травы, облаков, береговых линий — всё это использует фрактальные алгоритмы, в основе которых лежат идеи Линденмайера.

Вопросы для размышления

Экспоненциальный рост строки. Если правило F → FF применяется n раз, строка содержит 2^n символов F. При n = 30 это больше миллиарда символов. Какова максимальная «глубина» L-системы, которую можно реально нарисовать на экране 4K (3840 × 2160 пикселей)?
Обратная задача. Дано готовое дерево (например, фотография дерева). Можно ли восстановить L-систему, которая его породила? Это задача так называемой «обратной L-системы» (L-system inference). Как бы вы подошли к её решению?
Детерминизм и случайность. Классическая L-система полностью детерминирована: тот же стартовый набор всегда даёт одно и то же дерево. Но в природе два папоротника никогда не идентичны. Как изменить модель, чтобы добавить случайность, сохранив «характер» растения?
Контекстные L-системы. В 2L-системе правило применяется, только если соседи символа совпадают с условием. Например: a < b > c → d значит «заменить b на d, если слева a, справа c». Придумайте, как с помощью 2L-системы смоделировать распространение волны возбуждения по цепочке клеток.
Мерность. Кривая Коха имеет размерность ≈1.26, поверхностный аналог (снежинок-поверхностей) — размерность между 2 и 3. Что, по-вашему, означает «быть объектом размерностью 2.5»? Как это связано с понятием «шероховатости» поверхности?
L-система и язык программирования. Напишите (или опишите псевдокодом) функцию, которая принимает аксиому, правила и число итераций, возвращает итоговую строку. Оцените её сложность по времени и памяти. Как оптимизировать, если нужно нарисовать n=10, но хранить полную строку невозможно?
Линденмайер и Боше. Джагадиш Чандра Боше в начале XX века настаивал, что растения «чувствуют» и реагируют на внешние раздражители — и фиксировал эти реакции крескографом. Линденмайер в 1968-м показал, что рост растений описывается формальными правилами. Противоречат ли эти два взгляда друг другу? Или они описывают разные уровни организации жизни?