L-жүйелер: Формалды грамматика және қайта жазу жүйесі
L-system
L жүйесі – формалды грамматика, өсімдіктердің өсуін модельдеуге арналған қайта жазу жүйесі. Фракталдарды жасауға, биологиялық құрылымдарды сипаттауға қолданылады.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы 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.
Шығу тегі
Биолог ретінде Линденмайер ашытқылар мен жіп тәрізді саңырауқұлақтармен жұмыс істеді және цианобактериялар, мысалы Анабаена катенула сияқты бактериялардың әртүрлі түрлерінің өсу үлгілерін зерттеді. 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.