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
константы : нет
аксиома : А
правила : (А → AB), (B → A)

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

п = 0: А
п = 1: АБ
п = 2: АБА
n = 3: АБАБ
n = 4: КРЫЛЬЯ
n = 5: ДВОЙНОЙ РАЗМЕР
n = 6: БОЛИ
п = 7

Пример 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 2 3 5 8 13 21 34 55 89 ...

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

Для каждой строки, если мы отсчитываем k -ю позицию от левого конца строки, значение определяется тем, попадает ли кратное золотому сечению в интервал . Соотношение А и Б также приближается к золотой середине.

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

Эта последовательность является локально катенативной последовательностью, поскольку , где это n -е поколение.

Пример 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 градусов.

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

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

Пример 3: Множество Кантора [ править ]

переменные : AB
константы : нет
start : A {начальная строка символов}
правила : (А → ABA), (B → BBB)

Пусть А означает «движение вперед», а Б означает «движение вперед».

получается знаменитый фрактальный набор Кантора на реальной прямой R. В результате

Пример 4: Кривая Коха [ править ]

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

переменные : F
константы : + −
начало : Ф
правила : (F → F+F−F−F+F)

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

п = 0:
Ф
Площадь Коха – 0 итераций
п = 1:
Ф+Ф−Ф−Ф+Ф
Площадь Коха – 1 итерация
п = 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
Площадь Коха – 2 итерации
п = 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
Площадь Коха – 3 итерации

Пример 5: Треугольник Серпинского [ править ]

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

переменные : FG
константы : + −
начало : F-G-G
правила : (F → F−G+F+G−F), (G → GG)
угол : 120°

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

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

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

переменные : AB
константы : + −
начало : А
правила : (A → B−A−B), (B → A+B+A)
угол : 60°

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

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

Пример 6: кривая дракона [ править ]

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

переменные : FG
константы : + −
начало : Ф
правила : (F → F+G), (G → FG)
угол : 90°

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

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

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

См. Также: Папоротник Барнсли.
переменные : XF
константы : + − [ ]
начало : Х
правила : (X → F+[[X]-X]-F[-FX]+X), (F → FF)
угол : 25°

Сначала вам нужно инициализировать пустой стек. Это соответствует методу LIFO (последний пришел, первый ушел) для добавления и удаления элементов. Здесь 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-системы на плоскости R 2 являются:

См. также [ править ]

Викискладе есть медиафайлы, связанные с L-системами .

Примечания [ править ]

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

Книги [ править ]

Внешние ссылки [ править ]

  1. ^ Прадал, Кристоф; Фурнье, Кристиан; Вальдурье, Патрик; Коэн-Булакиа, Сара (2015). «ОпенАлеа». Материалы 27-й Международной конференции по управлению научными и статистическими базами данных (PDF) . стр. 1–6. дои : 10.1145/2791347.2791365 . ISBN  9781450337090 . S2CID   14246115 . Архивировано (PDF) из оригинала 17 октября 2019 г.
  2. ^ Будон, Фредерик; Прадал, Кристоф; Кокелаер, Томас; Прусинкевич, Пшемыслав; Годен, Кристоф (2012). «L-Py: среда моделирования L-системы для моделирования разработки архитектуры предприятия на основе динамического языка» . Границы в науке о растениях . 3 : 76. doi : 10.3389/fpls.2012.00076 . ПМЦ   3362793 . ПМИД   22670147 .
Retrieved from "https://en.wikipedia.org/w/index.php?title=L-system&oldid=1206282949"