Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Система переписывания и тип формальной грамматики
Rewriting system and type of formal grammar
L-система, или система Линденмайера, — это система параллельного переписывания и тип формальной грамматики. L-система состоит из алфавита символов, используемых для создания строк, набора правил подстановки, расширяющих каждый символ в более длинную строку символов, начальной "аксиомы", с которой начинается построение, и механизма для преобразования сгенерированных строк в геометрические структуры. L-системы были введены и разработаны в 1968 году Аристидом Линденмайером, венгерским теоретическим биологом и ботаником из Университета Утрехта. Линденмайер использовал L-системы для описания поведения растительных клеток и моделирования процессов роста растений. L-системы также применялись для моделирования морфологии различных организмов и могут использоваться для генерации самоподобных фракталов.
An L system or Lindenmayer system is a parallel rewriting system and a type of formal grammar. An L system consists of an alphabet of symbols that can be used to make strings, a collection of production rules that expand each symbol into some larger string of symbols, an initial "axiom" string from which to begin construction, and a mechanism for translating the generated strings into geometric structures. L systems were introduced and developed in 1968 by Aristid Lindenmayer, a Hungarian theoretical biologist and botanist at the University of Utrecht. Lindenmayer used L systems to describe the behaviour of plant cells and to model the growth processes of plant development. L systems have also been used to model the morphology of a variety of organisms and can be used to generate self similar fractals.
Происхождение
Будучи биологом, Линденмайер работал с дрожжами и нитевидными грибами и изучал закономерности роста различных типов бактерий, таких как цианобактерия Anabaena catenula. Изначально L-системы были созданы для формального описания развития таких простых многоклеточных организмов и иллюстрации взаимосвязей между растительными клетками. Впоследствии эта система была расширена для описания высших растений и сложных разветвленных структур.
As a biologist, Lindenmayer worked with yeast and filamentous fungi and studied the growth patterns of various types of bacteria, such as the cyanobacteria Anabaena catenula. Originally, the L systems were devised to provide a formal description of the development of such simple multicellular organisms, and to illustrate the neighbourhood relationships between plant cells. Later on, this system was extended to describe higher plants and complex branching structures.
Вариации
Разработано несколько усовершенствований этой базовой техники L-систем, которые могут использоваться как по отдельности, так и в сочетании друг с другом. К ним относятся стохастические грамматики, контекстно-зависимые грамматики и параметрические грамматики.
A number of elaborations on this basic L system technique have been developed which can be used in conjunction with each other. Among these are stochastic grammars, context sensitive grammars, and parametric grammars.
Двунаправленные грамматики
Би-направленная модель чётко разделяет символическую систему переписывания и назначение формы. Например, процесс переписывания строк в Примере 2 (Фрактальное дерево) не зависит от того, каким образом графические операции сопоставляются символам. Иными словами, к заданной системе переписывания применимо бесконечное количество методов визуализации. Би-направленная модель состоит из 1) прямого процесса, который строит дерево вывода с использованием правил продукции, и 2) обратного процесса, который реализует это дерево, последовательно назначая формы (от листьев к корню). Каждый шаг обратного вывода требует существенных геометрико-топологических рассуждений. В рамках этой би-направленной структуры ограничения и цели проектирования кодируются в грамматическом преобразовании формы. В задачах архитектурного проектирования би-направленная грамматика обеспечивает согласованную внутреннюю связность и богатую пространственную иерархию.
The bi directional model explicitly separates the symbolic rewriting system from the shape assignment. For example, the string rewriting process in the Example 2 (Fractal tree) is independent on how graphical operations are assigned to the symbols. In other words, an infinite number of draw methods are applicable to a given rewriting system. The bi directional model consists of 1) a forward process constructs the derivation tree with production rules, and 2) a backward process realizes the tree with shapes in a stepwise manner (from leaves to the root). Each inverse derivation step involves essential geometric topological reasoning. With this bi directional framework, design constraints and objectives are encoded in the grammar shape translation. In architectural design applications, the bi directional grammar features consistent interior connectivity and a rich spatial hierarchy.
Открытые проблемы
Существует множество нерешенных задач, связанных с изучением L-систем. Например:
There are many open problems involving studies of L systems. For example:
Характеризация всех детерминированных контекстно-свободных L-систем, которые локально конкатенируемы. (Полное решение известно только в случае, когда имеется только две переменные). Для заданной структуры найти L-систему, способную её породить.
Characterisation of all the deterministic context free L systems which are locally catenative. (A complete solution is known only in the case where there are only two variables). Given a structure, find an L system that can produce that structure.