L-система

Система переписывания и тип формальной грамматики

Деревья L-системы формируют реалистичные модели природных узоров

L -система или система Линденмайера — это параллельная система переписывания и тип формальной грамматики . L-система состоит из алфавита символов, которые могут быть использованы для создания строк , набора правил производства , которые расширяют каждый символ в некоторую большую строку символов, начальной строки « аксиомы », с которой начинается построение, и механизма для перевода сгенерированных строк в геометрические структуры. L-системы были введены и разработаны в 1968 году Аристидом Линденмайером , венгерским биологом -теоретиком и ботаником из Утрехтского университета . ^[1] Линденмайер использовал L-системы для описания поведения растительных клеток и для моделирования процессов роста растений . L-системы также использовались для моделирования морфологии различных организмов ^[2] и могут быть использованы для создания самоподобных фракталов .

Происхождение

«Сорняки», созданные с помощью L-системы в 3D.

Как биолог, Линденмайер работал с дрожжами и нитчатыми грибами и изучал закономерности роста различных типов бактерий , таких как цианобактерия Anabaena catenula . Первоначально L-системы были разработаны для формального описания развития таких простых многоклеточных организмов и для иллюстрации соседских отношений между растительными клетками. Позднее эта система была расширена для описания высших растений и сложных ветвящихся структур.

Структура L-системы

Рекурсивная природа правил L-системы приводит к самоподобию , и, таким образом, фракталоподобные формы легко описать с помощью L-системы. Модели растений и естественно выглядящие органические формы легко определить, поскольку с увеличением уровня рекурсии форма медленно «растет» и становится более сложной. Системы Линденмайера также популярны в создании искусственной жизни .

Грамматики L-системы очень похожи на полу-грамматику Туэ (см. Иерархия Хомского ). L-системы теперь широко известны как параметрические L-системы, определяемые как кортеж

G = ( V , ω, P ),

где

• V ( алфавит ) — это набор символов, содержащий как заменяемые элементы ( переменные ), так и не заменяемые («константы» или «терминалы»).
• ω ( старт , аксиома или инициатор ) — строка символов из V, определяющая начальное состояние системы
• P — это набор правил продукции или продукций, определяющих способ замены переменных комбинациями констант и других переменных. Продукция состоит из двух строк, предшествующей и последующей . Для любого символа A, который является членом множества V, который не появляется в левой части продукции в P, предполагается тождественная продукция A → A; эти символы называются константами или терминалами . (См. Закон тождества ).

Правила грамматики L-системы применяются итеративно, начиная с начального состояния. Одновременно применяется как можно больше правил, за одну итерацию. Тот факт, что каждая итерация использует как можно больше правил, отличает L-систему от формального языка, сгенерированного формальной грамматикой , которая применяет только одно правило за одну итерацию. Если бы правила производства применялись только по одному за раз, можно было бы просто сгенерировать строку в языке, и все такие последовательности применений производили бы язык, указанный грамматикой. Однако в некоторых языках есть некоторые строки, которые не могут быть сгенерированы, если грамматика рассматривается как L-система, а не как языковая спецификация. Например, ^[3] предположим, что в грамматике есть правило S→SS. Если производства выполняются по одному за раз, то, начиная с S, мы можем получить сначала SS, а затем, применяя правило снова, SSS. Однако, если все применимые правила применяются на каждом шаге, как в L-системе, то мы не можем получить эту сентенциальную форму. Вместо этого первый шаг даст нам SS, но второй применит правило дважды, давая нам SSSS. Таким образом, набор строк, произведенных L-системой из заданной грамматики, является подмножеством формального языка, определенного грамматикой, и если мы берем язык, который определяется как набор строк, это означает, что заданная L-система фактически является подмножеством формального языка, определенного грамматикой L-системы.

L-система является контекстно-свободной , если каждое правило производства относится только к отдельному символу, а не к его соседям. Таким образом, контекстно-свободные L-системы определяются контекстно-свободной грамматикой . Если правило зависит не только от одного символа, но и от его соседей, оно называется контекстно-зависимой L-системой.

Если для каждого символа существует ровно одно произведение, то L-система называется детерминированной (детерминированная контекстно-свободная L-система обычно называется системой D0L ). Если их несколько, и каждое выбирается с определенной вероятностью во время каждой итерации, то это стохастическая L-система.

Использование L-систем для создания графических изображений требует, чтобы символы в модели ссылались на элементы рисунка на экране компьютера. Например, программа Fractint использует графику черепахи (похожую на ту, что есть в языке программирования Logo ) для создания изображений на экране. Она интерпретирует каждую константу в модели L-системы как команду черепахи.

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

Пример 1: водоросли

Оригинальная L-система Линденмайера для моделирования роста водорослей.

переменные  : AB

константы  : нет

аксиома  : А

правила  : (А → АВ), (Б → А)

который производит:

n = 0 : А

n = 1 : АВ

n = 2 : АБА

n = 3 : АБААБ

n = 4 : АБАБАБАБ

n = 5 : АБААБАБАБАБ

n = 6 : АБААБ ...

n = 7 : АБААБАБААБААБАБААБАБААБААБАБАААБ

Пример 1: водоросли, объяснение

n=0: Начало (аксиома/инициатор) / \n=1: AB — начальный одиночный A, порожденный в AB по правилу (A → AB), правило (B → A) не может быть применено /| \n=2: ABA бывшая строка AB со всеми примененными правилами, A снова порождена в AB, бывшая B превратилась в A / | | | \n=3: ABAAB обратите внимание, что все A в первую очередь создают копию самих себя, затем B, который превращается ... / | | | \ | \ \n=4: ABAABABA ... в A одним поколением позже, начиная порождать/повторять/рекурсировать затем

Результатом является последовательность слов Фибоначчи . Если мы посчитаем длину каждой строки, то получим знаменитую последовательность чисел Фибоначчи (пропуская первую 1 из-за нашего выбора аксиомы):

1 2 3 5 8 13 21 34 55 89 ...

Если мы не хотим пропускать первую 1, мы можем использовать аксиому B. Это поместит узел B перед самым верхним узлом ( A ) графа выше.

Для каждой строки, если мы отсчитываем k -ю позицию от левого конца строки, значение определяется тем, попадает ли кратное золотого сечения в интервал . Отношение A к B также сходится к золотому сечению. ${\displaystyle (k-1,k)}$

Этот пример дает тот же результат (с точки зрения длины каждой строки, а не последовательности A и B ), если правило ( A → AB ) заменить на ( A → BA ), за исключением того, что строки зеркально отражаются.

Эта последовательность является локально катенативной последовательностью , поскольку , где — n -е поколение. ${\displaystyle G(n)=G(n-1)G(n-2)}$ ${\displaystyle G(n)}$

Пример 2: фрактальное (бинарное) дерево

• переменные  : 0, 1
• константы : "[", "]"
• аксиома  : 0
• правила  : (1 → 11), (0 → 1[0]0)

Форма строится путем рекурсивной подачи аксиомы через правила производства. Каждый символ входной строки проверяется по списку правил, чтобы определить, каким символом или строкой его заменить в выходной строке. В этом примере «1» во входной строке становится «11» в выходной строке, а «[» остается прежним. Применяя это к аксиоме «0», получаем:

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

• 0: нарисовать отрезок линии , заканчивающийся листом
• 1: нарисуйте отрезок линии
• [: толкнуть положение и угол, повернуть влево на 45 градусов
• ]: позиция и угол выталкивания, поворот вправо на 45 градусов

Push и pop ссылаются на стек LIFO (более техническая грамматика имела бы отдельные символы для «push position» и «turn left»). Когда интерпретация черепахи встречает '[', текущее положение и угол сохраняются, а затем восстанавливаются, когда интерпретация встречает ']'. Если было «задвинуто» несколько значений, то «pop» восстанавливает последние сохраненные значения. Применяя графические правила, перечисленные выше, к более ранней рекурсии, мы получаем:

• 
  Аксиома
• 
  Первая рекурсия
• 
  Вторая рекурсия
• 
  Третья рекурсия
• 
  Четвертая рекурсия
• 
  Седьмая рекурсия, уменьшенная в десять раз

Пример 3: множество Кантора

переменные  : AB

константы  : нет

начало  : A {начальная строка символов}

правила  : (A → ABA), (B → BBB)

Пусть A означает «тянуть вперед», а B означает «двигаться вперед».

Это создает знаменитое фрактальное множество Кантора на действительной прямой R.

Пример 4: кривая Коха

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

переменные  : F

константы  : + −

начало  : F

правила  : (Ф → Ф+Ф−Ф−Ф+Ф)

Здесь F означает «тянуться вперед», + означает «повернуться налево на 90°», а − означает «повернуться направо на 90°» (см. графику черепахи ).

н = 0:

Ф

п = 1:

Ф+Ф−Ф−Ф+Ф

п = 2:

Ф+Ф−Ф−Ф+Ф+Ф−Ф−Ф+Ф−Ф+Ф−Ф−Ф+Ф−Ф−Ф+Ф−Ф−Ф+Ф+Ф−Ф−Ф+Ф

п = 3:

Ф+Ф−Ф−Ф+Ф+Ф−Ф−Ф+Ф−Ф+Ф−Ф−Ф+Ф−Ф−Ф+Ф−Ф−Ф+Ф+Ф−Ф−Ф+Ф+

Ф+Ф−Ф−Ф+Ф+Ф−Ф−Ф+Ф−Ф+Ф−Ф−Ф+Ф−Ф−Ф+Ф−Ф−Ф+Ф+Ф−Ф−Ф+Ф−

Ф+Ф−Ф−Ф+Ф+Ф−Ф−Ф+Ф−Ф+Ф−Ф−Ф+Ф−Ф−Ф+Ф−Ф−Ф+Ф+Ф−Ф−Ф+Ф−

Ф+Ф−Ф−Ф+Ф+Ф−Ф−Ф+Ф−Ф+Ф−Ф−Ф+Ф−Ф−Ф+Ф−Ф−Ф+Ф+Ф−Ф−Ф+Ф+

Ф+Ф−Ф−Ф+Ф+Ф−Ф−Ф+Ф−Ф+Ф−Ф−Ф+Ф−Ф−Ф+Ф−Ф−Ф+Ф+Ф−Ф−Ф+Ф

Пример 5: Треугольник Серпинского

Треугольник Серпинского, нарисованный с использованием L-системы.

переменные  : FG

константы  : + −

начало  : Ф−Г−Г

правила  : (Ф → Ф−Г+Ф+Г−Ф), (Г → ГГ)

угол  : 120°

Здесь F и G оба означают «тянуться вперед», + означает «повернуть налево на угол», а − означает «повернуть направо на угол».

• 
  п = 2
• 
  п = 4
• 
  п = 6

Также возможно аппроксимировать треугольник Серпинского с помощью L-системы стреловидных кривых Серпинского .

переменные  : AB

константы  : + −

начало  : А

правила  : (А → Б−А−Б), (Б → А+Б+А)

угол  : 60°

Здесь A и B оба означают «тянуться вперед», + означает «повернуть налево на угол», а − означает «повернуть направо на угол» (см. графику черепахи ).

Эволюция для n = 2, n = 4, n = 6, n = 8

Пример 6: кривая дракона

Кривая дракона , нарисованная с использованием L-системы.

переменные  : FG

константы  : + −

начало  : F

правила  : (Ф → Ф+Г), (Г → ФГ)

угол  : 90°

Здесь F и G оба означают «тянуться вперед», + означает «повернуть налево на угол», а − означает «повернуть направо на угол».

Кривая дракона для n = 10

Пример 7: фрактальное растение

переменные  : XF

константы  : + − [ ]

начало  : X

правила  : (X → F+[[X]-X]-F[-FX]+X), (F → FF)

угол  : 25°

Сначала вам нужно инициализировать пустой стек. Это следует методу LIFO (Last in, First Out) для добавления и удаления элементов. Здесь F означает «рисовать вперед», − означает «повернуть направо на 25°», а + означает «повернуть налево на 25°». X не соответствует никакому действию рисования и используется для управления эволюцией кривой. Квадратная скобка «[» соответствует сохранению текущих значений положения и угла, поэтому вы помещаете положение и угол наверх стека, когда встречается токен «]», выталкиваете стек и сбрасываете положение и угол. Каждый токен «[» предшествует каждому токену «]».

Фрактальное растение для n = 6

Вариации

Разработан ряд усовершенствований этой базовой техники L-системы, которые могут использоваться совместно друг с другом. Среди них — стохастические грамматики , контекстно-зависимые грамматики и параметрические грамматики.

Стохастические грамматики

Модель грамматики, которую мы обсуждали до сих пор, была детерминированной — то есть, для любого символа в алфавите грамматики было ровно одно правило производства, которое всегда выбирается и всегда выполняет одно и то же преобразование. Одна из альтернатив — указать более одного правила производства для символа, задав каждому вероятность появления. Например, в грамматике примера 2 мы могли бы изменить правило для переписывания «0» с:

0 → 1[0]0

вероятностному правилу:

0 (0,5) → 1[0]0

0 (0,5) → 0

При таком производстве, всякий раз, когда во время переписывания строки встречается "0", существует 50% вероятность того, что он будет вести себя так, как описано ранее, и 50% вероятность того, что он не изменится во время производства. Когда стохастическая грамматика используется в эволюционном контексте, целесообразно включить случайное семя в генотип , чтобы стохастические свойства изображения оставались постоянными между поколениями.

Контекстно-зависимые грамматики

Правило производства, чувствительное к контексту, смотрит не только на изменяемый им символ, но и на символы в строке, которые появляются до и после него. Например, правило производства:

б < а > с → аа

преобразует «a» в «aa», но только если «a» встречается между «b» и «c» во входной строке:

…назад…

Как и в случае со стохастическими постановками, существует несколько постановок для обработки символов в разных контекстах. Если для заданного контекста не найдено правило постановки, предполагается постановка тождества, и символ не изменяется при преобразовании. Если в одной и той же грамматике существуют как контекстно-зависимые, так и контекстно-свободные постановки, предполагается, что контекстно-зависимые постановки имеют приоритет, когда они применимы.

Параметрические грамматики

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

а(0,1)[б(0,0)]а(1,2)

Параметры могут использоваться функциями рисования, а также правилами производства. Правила производства могут использовать параметры двумя способами: во-первых, в условном операторе, определяющем, будет ли применяться правило, и, во-вторых, правило производства может изменять фактические параметры. Например, посмотрите на:

a(x,y) : x == 0 → a(1, y+1)b(2,3)

Модуль a(x,y) подвергается преобразованию по этому правилу производства, если выполняется условие x=0. Например, a(0,2) подвергнется преобразованию, а a(1,2) — нет.

В части преобразования правила производства могут быть затронуты как параметры, так и целые модули. В приведенном выше примере модуль b(x,y) добавляется к строке с начальными параметрами (2,3). Также преобразуются параметры уже существующего модуля. Согласно правилу производства выше,

а(0,2)

Становится

а(1,3)б(2,3)

поскольку параметр «x» функции a(x,y) явно преобразуется в «1», а параметр «y» функции a увеличивается на единицу.

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

Двунаправленные грамматики

Двунаправленная модель явно разделяет символическую систему переписывания от назначения формы. Например, процесс переписывания строки в примере 2 (фрактальное дерево) не зависит от того, как графические операции назначаются символам. Другими словами, бесконечное число методов рисования применимо к данной системе переписывания.

Двунаправленная модель состоит из 1) прямого процесса, который создает дерево вывода с правилами производства, и 2) обратного процесса, который реализует дерево с формами поэтапно (от листьев к корню). Каждый шаг обратного вывода включает в себя существенные геометрические и топологические рассуждения. С помощью этой двунаправленной структуры ограничения и цели проектирования кодируются в переводе грамматики в форму. В приложениях архитектурного проектирования двунаправленная грамматика характеризуется последовательной внутренней связностью и богатой пространственной иерархией. ^[4]

Открытые проблемы

Существует много открытых проблем, связанных с изучением L-систем. Например:

• Характеристика всех детерминированных контекстно-свободных L-систем, которые локально катенативны . (Полное решение известно только в случае, когда есть только две переменные). ^[5]
• При наличии структуры найдите L-систему, которая может создать эту структуру. ^{[ необходима цитата ]}

Типы L-систем

L-системы на действительной прямой R :

• Система Пруэ-Туэ-Морзе

Известными L-системами на плоскости ^R2 являются :

• кривые, заполняющие пространство ( кривая Гильберта , кривые Пеано , церковь Деккинга, коламы ),
• кривые, заполняющие медианное пространство ( кривая Леви С , кривая дракона Хартера-Хайвея , тердрагон Дэвиса-Кнута),
• мозаика ( мозаика сфинкса , мозаика Пенроуза )

Смотрите также

• Цифровой морфогенез
• Фрактал
• Система итерированных функций
• кривая Гильберта
• Система реакции-диффузии  – тип математической модели, которая обеспечивает моделирование диффузии химических реагентов (в том числе реалистичное)
• Стохастическая контекстно-свободная грамматика
• SpeedTree
• Алгоритмическая красота растений

Примечания

1. Линденмайер, Аристид (март 1968). «Математические модели клеточных взаимодействий в развитии II. Простые и ветвящиеся нити с двусторонними входами». Журнал теоретической биологии . 18 (3): 300–315. Bibcode : 1968JThBi..18..300L. doi : 10.1016/0022-5193(68)90080-5. ISSN  0022-5193. PMID  5659072.
2. Гжегож Розенберг и Арто Саломаа. Математическая теория L-систем (Academic Press, Нью-Йорк, 1980). ISBN 0-12-597140-0 
3. "L-системы". Энциклопедия математики . Springer . Получено 26 июля 2022 г.
4. Хуа, Х., 2017, декабрь. Двунаправленная процедурная модель для архитектурного проектирования. В Computer Graphics Forum (т. 36, № 8, стр. 219-231).
5. Кари, Лила; Розенберг, Гжегож; Саломаа, Арто (1997). «L Systems». Справочник по формальным языкам . С. 253–328. doi :10.1007/978-3-642-59136-5_5. ISBN 978-3-642-63863-3.

Книги

• Пшемыслав Прусинкевич , Аристид Линденмайер — Алгоритмическая красота растений PDF-версия доступна бесплатно здесь. Архивировано 10 апреля 2021 г. на Wayback Machine
• Гжегож Розенберг , Арто Саломаа – Системы Линденмайера: влияние на теоретическую информатику, компьютерную графику и биологию развития ISBN 978-3-540-55320-5 
• Д.С. Эберт, Ф.К. Масгрейв и др. – Текстурирование и моделирование: процедурный подход , ISBN 0-12-228730-4 
• Берри, Джейн, Берри Марк, (2010). Новая математика архитектуры, Нью-Йорк: Темза и Гудзон.
• Аристид Линденмайер, «Математические модели клеточного взаимодействия в развитии». J. Theoret. Biology, 18:280—315, 1968.

Внешние ссылки

• Алгоритмическая ботаника в Университете Калгари
• L-Systems: удобная для пользователя страница для создания фракталов и растений из L-Systems.
• Ветвление: дерево L-системы. Java-апплет и его исходный код ( с открытым исходным кодом ) моделирования роста ботанического дерева с использованием L-системы.
• Fractint L-System True Fractals
• OpenAlea Архивировано 17 октября 2005 г. на Wayback Machine : среда программного обеспечения с открытым исходным кодом для моделирования растений, ^[1] которая содержит L-Py, реализацию систем Lindenmayer на Python с открытым исходным кодом ^[2]
• "powerPlant" — программное обеспечение с открытым исходным кодом для моделирования ландшафта
• Домашняя страница Fractint
• Простой генератор L-систем (Windows)
• Lyndyhop: еще один простой генератор L-систем (Windows и Mac)
• Генератор эволюционных L-систем (anyos*)
• Реализация L-систем в Racket
• Гриффитс, Дэйв (2004). "LsystemComposition". Pawfal . Архивировано из оригинала 2004-11-06 . Получено 2012-04-19 .Страница об использовании L-систем и генетических алгоритмов для генерации музыки.
• eXtended L-Systems (XL), грамматики реляционного роста и программная платформа с открытым исходным кодом GroIMP.
• Апплет JAVA с множеством фрактальных фигур, созданных L-системами. Архивировано 2016-08-06 на Wayback Machine
• My Graphics – приложение для iPhone/iPad, которое генерирует несколько графических шаблонов L-системы.
• Манусакис, Стелиос (июнь 2006 г.). Музыкальные L-системы (PDF) (дипломная работа). Королевская консерватория Гааги . Архивировано (PDF) из оригинала 2011-07-23 . Получено 2022-07-19 .
• Онлайн-эксперименты с L-Systems с использованием JSXGraph (JavaScript)
• Flea Реализация LSYSTEM на Ruby, использующая предметно-ориентированный язык вместо кратких команд генератора.
• Электростанция Lindenmaer и фрактальный генератор с использованием L-систем (JavaScript)
• Розенберг, Г.; Саломаа, А. (2001) [1994], "L-системы", Энциклопедия математики , EMS Press
• L-Parser Лоренса Лапре Архивировано 2013-09-13 на Wayback Machine
• HTML5 L-Systems – попробуйте поэкспериментировать онлайн
• Программа векторной графики Inkscape оснащена L-System Parser
• Лиу, Чэн-Юань; У, Тай-Хэй; Ли, Чиа-Ин (2009). «Моделирование сложности в музыкальном ритме». Сложность . 15 (4): 19–30. doi :10.1002/cplx.20291. S2CID  18737938.
• Реализация парсера L-системы и простой графики черепахи на языке программирования Icon
• Генератор системы Линденмейера Нолана Кэрролла
• Bloogen: L-системы с генетическим уклоном

1. Прадаль, Кристоф; Фурнье, Кристиан; Вальдюрье, Патрик; Коэн-Булакиа, Сара (2015). "OpenAlea". Труды 27-й Международной конференции по управлению научными и статистическими базами данных (PDF) . стр. 1–6. doi :10.1145/2791347.2791365. ISBN 9781450337090. S2CID  14246115. Архивировано (PDF) из оригинала 17.10.2019.
2. Будон, Фредерик; Прадаль, Кристоф; Кокелар, Томас; Прусинкевич, Пшемыслав; Годин, Кристоф (2012). "L-Py: фреймворк моделирования L-систем для моделирования разработки архитектуры растений на основе динамического языка". Frontiers in Plant Science . 3 : 76. doi : 10.3389/fpls.2012.00076 . PMC 3362793 . PMID  22670147.