L-система - L-system

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

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

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

L-системная структура

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

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

G = ( V , ω, P ),

куда

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

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

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

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

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

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

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

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

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

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

аксиома  : A

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

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

п = 0: А

n = 1: AB

n = 2: ABA

n = 3: ABAAB

n = 4: ABAABABA

n = 5: ABAABABAABAAB

n = 6: ABAABABAABAABABAABABA

n = 7: ABAABABAABAABABAABABAABAABABAABAAB

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

n=0:               A             start (axiom/initiator)
                  / \
n=1:             A   B           the initial single A spawned into AB by rule (A → AB), rule (B → A) couldn't be applied
                /|     \
n=2:           A B      A        former string AB with all rules applied, A spawned into AB again, former B turned into A
             / | |       | \
n=3:         A B A       A B     note all A's producing a copy of themselves in the first place, then a B, which turns ...
           / | | | \     | \ \
n=4:       A B A A B     A B A   ... into an A one generation later, starting to spawn/repeat/recurse then

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

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

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

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

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

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

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

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

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

аксиома:	0
1-я рекурсия:	1 [0] 0
2-я рекурсия:	11 [1 [0] 0] 1 [0] 0
3-я рекурсия:	1111 [11 [1 [0] 0] 1 [0] 0] 11 [1 [0] 0] 1 [0] 0
…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

начало  : F

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

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

п = 0:

F

п = 1:

F + F − F − F + F

п = 2:

F + F − F − F + F + F + F − F − F + F − F + F − F − F + F − F + F − F − F + F + F + F − F − F + F

п = 3:

F + F − F − F + F + F + F − F − F + F − F + F − F − F + F − F + F − F − F + F + F + F − F − F + F +

F + F − F − F + F + F + F − F − F + F − F + F − F − F + F − F + F − F − F + F + F + F − F − F + F−

F + F − F − F + F + F + F − F − F + F − F + F − F − F + F − F + F − F − F + F + F + F − F − F + F−

F + F − F − F + F + F + F − F − F + F − F + F − F − F + F − F + F − F − F + F + F + F − F − F + F +

F + F − F − F + F + F + F − F − F + F − F + F − F − F + F − F + F − F − F + F + F + F − F − F + F

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

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

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

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

начать  : F-G-G

правила  : (F → F − G + F + G − F), (G → GG)

угол  : 120 °

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

• 

  п = 2

• 

  п = 4

• 

  п = 6

Кроме того , можно аппроксимировать треугольник Серпинского , используя кривую Arrowhead Серпинского L-систему.

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

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

начало  : A

правила  : (A → B − A − B), (B → A + B + A)

Угол  : 60 °

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

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

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

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

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

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

начало  : F

правила  : (F → F + G), (G → FG)

Угол  : 90 °

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

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

Пример 7: Фрактальный завод

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

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

начало  : X

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

угол  : 25 °

Здесь 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)

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

а (х, у): х == 0 → а (1, у + 1) Ь (2,3)

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

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

а (0,2)

Становится

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

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

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

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

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

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

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

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

• Характеристика всех детерминированных контекстно-свободных L-систем, которые являются локально связанными . (Полное решение известно только в том случае, если есть только две переменные).
• Для данной структуры найдите L-систему, которая может создать эту структуру.

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

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

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

Хорошо известными L-системами на плоскости R ² являются:

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

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

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

Примечания

Книги

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

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