СИСТЕМЫ ЛИНДЕМАЙЕРА

Л–системы лежат на стыке таких сфер математики, как эволюционные методы и формальная грамматика.

Л–системы были описаны в 1968 году венгерским ботаником Аристидом Линденмайером для изучения развития простых многоклеточных организмов, позже базис Л–систем был расширен для моделирования сложных ветвящихся структур — разнообразных деревьев и цветов. Впервые для решения задач автоматической генерации музыки их применил в своей диссертации 1996 года американский программист и композитор Люк Дюбуа.

В основе работы Л–систем лежит набор правил замещения, рекурсивно применяющийся на начальную строку символов и интерпретирующий конечную строку, как структурные элементы организма. Правила замещения определяют как каждый конкретный символ в текущем поколении должен быть перемещен. Базовое описание контекстно–независимой системы заключается в формуле:

G = |A, P, α|

где А — алфавит системы (набор всех символов включая пустой символ, ε), Р — это конечной набор правил замещения (определенный в виде входящий символ — выходящий символ1, выходящий символn ), и α — символ или строка из алфавита, используемая в качестве начального состояния. Также в работе алгоритма участвуют A* — набор всех возможных символов строк из А, А+ — набор всех возможных символьных строк без пустого символа. Л–системы не имеют конечных символов, хотя конечный символ может быть эмулирован путем замены текущего символа на самого себя.

Так как чаще всего Л–системы используются для моделирования роста растений, раковин моллюсков, пчелиных сот и т.д., основным представлением работы Л–системы является графическое. Чаще всего для этого используется так называемый «черепаший язык». Черепаха находится на координатной плоскости и может передвигаться по ней только вперёд, но может также поворачиваться на месте. При движении черепаха способна чертить линию карандашом, или двигаться, не оставляя за собой след. Есть возможность заменять карандаши и тем самым управлять толщиной линии и её цветом. «Черепаший язык» является основой языка программирования LOGO.

Основные команды передаваемые «черепахе» следующие:

F — один шаг вперед — рисование сегмента линии;

ψ — задание угла для поворота черепахи;

+ — поворот влево на заданный угол;

– — поворот вправо на заданный угол;

[ — сохранение заданной позиции и угла;

] — восстановление исходных позиций;

/ — глубина итерации.

В качестве примера можно привести простую систему, имитирующую рост водорослей «ряска» на стоячей воде:

символы — A B;

начальное положение — A;

правила замещения — (A → AB), (B → A);

В итоге получаем следующую последовательность поколений:

Поколение	Состояние
0	A
1	AB
2	ABA
3	ABAAB
4	ABAABABA
5	ABAABABAABAAB
6	ABAABABAABAABABAABABAABAABABAABAAB

Л–системы делятся на несколько видов.

Контекстно–независимые и чувствительные к контексту. Л–система называется контекстно–независимой (0Л–системой), если замещение происходит независимо от окружающих символов. Л–система называется чувствительной к контексту, если правила замещения определяются положением символа, который следует заменить (например, заменить A на ABA, если A стоит после B).

Л–система называется стохастической, если возможны несколько правил для каждого символа–предшественника. Одно из нескольких правил для данного символа строки состояния каждый раз выбирается случайно с некоторой заданной вероятностью. Само собой, каждому из правил для данного предшественника приписывается вероятность выбора правила — число от нуля до единицы (сумма таких чисел должна равняться единице).

Параметрической называется Л–система, в которой начальный набор символов может меняться — например, путем ввода новых символов в зависимости от определенных условий.

ПРименение Л–систем для генерации алгоритмических композиций подразумевает использование вместо символов определенных музыкальных параметров. Например, профессор Португальского университета Педро Пестана назначает алфавит из семи символов — нот, входящих в гамму до мажор, а правила замещения определяет исходя из матрицы переходных вероятностей.

Другим воплощением Л–систем в алгоритмической композиции является программа LMUSE Дэвида Шарпа, в которой различные музыкальные параметры, такие, как высота, продолжительность, и громкость могут быть назначены различным компонентам положения, толщины линии и т.д. В данную программу заложено около 20 команд направлений, 10 команд движений, а также около 10 команд, относящихся только к музыкальному воплощению.

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