L-системаL-система или система Линденмайера — это параллельная система переписывания и вид формальной грамматики. L-система состоит из алфавита символов, которые могут быть использованы для создания строк, набора порождающих правил[англ.], которые задают правила подстановки вместо каждого символа, начальной строки («аксиомы»), с которой начинается построение, и механизма перевода образованной строки в геометрические структуры. L-системы предложил и развивал в 1968 Аристид Линденмайер, венгерский биолог и ботаник из Утрехтского университета. Линденмайер использовал L-системы для описания поведения клеток растений и моделирования процесса развития растения[англ.]. L-системы использовались также для моделирования морфологии различных организмов[1] и могут быть использованы для генерации самоподобных фракталов, таких как системы итерируемых функций[англ.]. ИстокиВ качестве биолога Линденмайер работал с дрожжами и нитевидными грибами и изучал схемы роста различных видов водорослей, таких как синезелёные водоросли Anabaena catenula. Первоначально L-системы были разработаны для формального описания развития таких простых многоклеточных организмов и для иллюстрации связи между соседними клетками растения. Позже система была расширена для описания высших растений и сложных ветвящихся структур. Структура L-системыРекурсивная природа правил L-системы приводит к самоподобию и потому подобные фракталам формы легко описываются с помощью L-системы. Модели растений и выглядящие естественно органические формы легко сформировать, так как при увеличении уровня рекурсии модель медленно «растёт» и становится более сложной. Системы Линденмайера популярны также в генерации искусственной жизни. Грамматики L-систем очень похожи на полусистемы Туэ[англ.] (см. «Иерархия Хомского»). L-системы теперь известны как параметрические L системы, которые определяются как кортеж
где
Правила грамматики L-системы применяются итеративно, начиная с аксиомы (начального состояния). На итерации применяется как можно больше правил. Факт, что на каждой итерации применяется как можно больше правил, отделяет L-систему от формального языка генерируемого по формальной грамматике, которая применяет только одно правило на итерацию. Если бы правила вывода применялись по одному, легко было бы сгенерировать язык, а не L-систему. Таким образом, L-системы являются подмножеством языков. L-система является контекстно-свободной, если каждое правило вывода ссылается только на индивидуальные символы, а не на их соседей. Контекстно-свободные L-системы определяются контекстно-свободной грамматикой. Если правило зависит не только от единичного символа, но и от соседних, система называется контекстно-зависимой L-системой. Если существует в точности одно правило для каждого символа, говорят, что L-система детерминированная (детерминированная контекстно-независимая L-система называется D0L системой[англ.]). Если имеется несколько правил и каждая выбирается с некоторой вероятностью на каждой итерации, то это стохастическая L-система. Чтобы использовать L-системы для генерации графических образов, требуется, чтобы символы в модели относились к элементам рисунка на экране компьютера. Например, программа Fractint[англ.] использует черепашью графику (похожую на графику в языке Лого) для получения изображения на экране. Программа интерпретирует каждую константу в модели L-системы как команды системы черепашьей графики. Примеры L-системПример 1: ВодорослиОригинальная L-система Линденмайера для моделирования роста водорослей.
Система даёт
Пример 1: Водоросли, объяснениеn=0: A старт (аксиома/инициатор) / \ n=1: A B начальная единственная A превращается в AB по правилу (A → AB), правило (B → A) не может быть применено /| \ n=2: A B A к строке AB применяются все правила, A снова превращается в AB, а B превращается A /| | |\ n=3: A B A A B заметьте, что все A переводятся в копию себя и добавляется B, которая превращается ... /| | |\ |\ \ n=4: A B A A B A B A ... в A в следующем поколении, что приводит к рекурсии Результатом будут слова Фибоначчи. Если посчитать длину каждой строки, получим знаменитую последовательность Фибоначчи (опуская первую 1):
Для каждой строки, если мы отсчитаем k-ю позицию с левого конца строки, значение зависит от того, попадает ли k, умноженное на золотое сечение, в интервал . Отношение вхождений букв A к B также сходится к золотому сечению. Этот пример даёт тот же результат (в смысле длины строк, не в смысле последовательности букв A и B), если правило (A → AB) заменить на (A → BA), но при этом получим зеркально отражённые строки. Эта последовательность является катенантной[англ.], поскольку , где является n-м поколением. Пример 2: Дерево Пифагора
Фигура строится рекурсивным применением правил вывода к аксиоме. Каждый символ входной строки проверяется в списке правил, чтобы определить, на что следует заменить символ. В этом примере «1» на входе превращается в «11» на выходе, а «[» не меняется. Применяя правила вывода к аксиоме «0», получим:
Мы видим, что строки быстро растут в длине и сложности. Строку можно нарисовать в виде рисунка с помощью черепашьей графики, где каждому символу соответствует графическая операция для черепахи. В данном примере черепахе могут быть даны следующие команды:
«Положим в стек» и «выберем из стека» относится к LIFO-стеку (более подробная грамматика потребовала бы разделить на «положим в стек» и «повернём»). Когда интерпретатор встречает «[», текущее положение черепахи и угол движения сохраняются в стеке, когда же встречается «]», положение и угол восстанавливаются. Если несколько значений заносятся в стек, восстанавливается последнее занесённое значение. В литературе L-системы, использующие такой подход к ветвлению, называют «bracketed L-systems» (скобочные L-системы)[2]. Применяя эти графические правила к полученной ранее строке, мы имеем:
Пример 3: Множество Кантора
Пусть A означает «рисуем отрезок», а B означает «движемся». Такая грамматика порождает знаменитое канторово фрактальное множество на вещественной оси R. Пример 4: Кривая КохаВариант кривой Коха, использующей только прямые углы.
Здесь F означает «рисуем отрезок», + означает «повернуть влево на 90°», а − означает «повернуть вправо на 90°» (см. «Черепашья графика»).
Пример 5: Треугольник СерпинскогоТреугольник Серпинского, нарисованный с помощью L-системы.
Здесь F и G означают «рисуем отрезок», + означает «повернуть вправо на угол», а − означает «повернуть влево на угол».
Можно также аппроксимировать треугольник Серпинского, используя L-систему создания стреловидной кривой Серпинского[англ.].
Здесь A и B означают «рисуем отрезок», + означает «повернуть влево на угол», а − означает «повернуть вправо на угол» (см. «Черепашья графика»). Пример 6: Кривая драконаКривая дракона, нарисованная с помощью L-системы.
Здесь F означает «рисуем отрезок», − означает «повернуть влево на 90°», а + означает «повернуть вправо на 90°». X и Y не соответствуют какому-либо действию при рисовании, а используются только для построения кривой. Пример 7: Фрактальное растение
Здесь F означает «рисуем отрезок», − означает «повернуть влево на 25°», а + означает «повернуть вправо на 25°». X не соответствует какому-либо действию при рисовании и используется только для построения кривой. Квадратная скобка "[" соответствует сохранению текущих значений позиции и угла, которые восстанавливаются, когда выполняется соответствующий символ «]». ВариантыБыло сделано несколько разработок на основе техники L-систем, которые могут быть использованы совместно. Среди них cтохастические грамматики[англ.], контекстно-зависимые грамматики и параметрические грамматики. Стохастические грамматикиМодели грамматик, которые мы сейчас рассматривали, являются детерминированными. То есть, если дан какой-либо символ из алфавита, имеется в точности одно правило, которое всегда выбирается и всегда выполняется одна и та же подстановка. Альтернативой является указание более одного правила вывода для символа, задав для каждого правила вероятность выполнения. Например, в грамматике примера 2 мы можем заменить правило переписывания «0» с
на вероятностное правило
При этих правилах вывода, когда встречается «0» во входной строке, с вероятностью 50 % поведение будет таким же, как и раньше, а с вероятностью 50 % ничего не меняется. Если используется стохастическая грамматика в контексте эволюции, рекомендуется инкорпорировать генератор случайности в генотип, так что стохастические свойства рисунка остаются постоянными между поколениями. Контекстно-зависимые грамматикиКонтекстно-зависимое правило вывода просматривает не только символы, которые он изменяет, но и символы предшествующие им и следующие за ними. Например, правило вывода:
преобразует «a» в «aa», но только если «a» окажется между «b» и «c» во входной строке:
Как и в случае случайного вывода, имеется несколько правил для обработки символы в различных контекстах. Если никакое порождающее правило не найдено для указанного контекста, предполагается тождественное преобразование, и символ не меняется. Если имеются как контекстно-независимые, так и зависимые правила вывода в той же грамматике, контекстно-зависимое правило вывода имеет преимущество (если его можно применить). Параметрические грамматикиВ параметрической грамматике каждый символ в алфавите имеет список параметров, ассоциированный с символом. Символ вместе с параметрами называется модулем и строка в параметрической грамматике — это последовательность модулей. Примером может служить следующая строка:
Параметры могут быть использованы как функцией рисования, так и правилами вывода. Правила вывода могут использовать параметры двумя путями. В первом случае параметр используется в условном выражении, определяющем, следует ли применять правило вывода. Во втором случае правило вывода может подменять фактические параметры. Например, правило вывода:
Модуль a(x,y) испытывает преобразование по этому правилу, если выполняется x=0. Например, a(0,2) претерпит преобразование, а a(1,2) — нет. На правой стороне правила вывода (в преемнике) могут быть подвергнуты преобразованию как параметры, так и целые модули. В примере выше модуль b(x,y) добавляется к строке с начальными параметрами (2,3). Параметры же уже существующего модуля преобразуются. При описанных выше правилах вывода,
Становится
так как параметр «x» модуля a(x,y) явно преобразуется в «1», а параметр «y» увеличивается на единицу. Параметрические грамматики позволяют длину отрезка и угол ответвления задать в грамматике, а не в методах интерпретации черепашьей графики. Если возраст также задаётся параметром для модуля, правила могут быть изменены в зависимости от возраста сегмента растения, что позволяет создавать анимацию всего жизненного цикла дерева. Другие категории L-систем
Открытые проблемыИмеется много открытых проблем, связанных с изучением L-систем. Например:
Ответы на эти вопросы интересны не только с теоретической точки зрения, они полезны также при построении pL-систем для создания рисунков с заданными свойствами[4]. Типы L-системL-системы на вещественной оси R: Общеизвестные L-системы на плоскости R2:
См. также
Примечания
Литература
Ссылки
|