What are L-grammars?

Download my L-grammars package (small DOS program and a VB script for CorelDRAW 9.0)

 

L-grammars (L-systems), named after Lindenmayer who introdiced that notion to science in the late sixties are a special kind of description of objects. No matter what objects - geometric, informational, chemical... even musical. But by nature they are very useful to model fractal objects.

 

The L-grammars is defined when determined:
1. Alphabet of L-grammars.
2. Initial sentence.
3. Rules of interchange.
4. Rules of interpretation (optional).

 

Let's see some examples. Assume in our L-grammars the symbol 'F' means 'draw an 1 cm line up (at 90 degrees)'; '+' or '-' means 'turn the direction of drawing at some arbitrary angle (hereinafter referred to as managing angle)', the symbol '[' instruct to remember the position (coordinates) of drawing and the symol ']' puts the cursor to the last stored coordinates.

That's all - the symbols 'F', '+', '-', '[' and ']' is the alphabet of our L-grammars. Let's now try to make L-system that will draw a square.

It's easy, you see: given managing angle 90 degrees and sequence F+F+F+F yields the desired square. This is a very simple object however. Now, what about more complicated fractal objects like the Koch curve (see it below, I will not enlarge on how it is constructed, there are a lot of information in the Web). Owing to its self-similar nature one can write a sequence that draw only a trivial segment: F+F--F+F will construct the following structure:. To obtain something like the construction below one should instruct the L-grammars to change the symbol 'F' with the initial sequence for several times. The output will looks like 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-...
Just honestly try to interprete this clause manually and you'll understand the whole thing (managing angle here is 60 degrees).

You see, each iteration add some complexity to your image, so have you ever need more complicated curve just add a few cycles to the L-grammar and get the more detailed fractal.

 

It’s time now to discuss the primary structure of nucleic acids.
As it was shown above, relatively simple rules lead one to rather complex structures like plant forms etc. You should become thinking, therefore, that perhaps genoms might had been constructed in a similar way. For example, given initial sequence ‘ACATG}’ and rules of interchange:

A --> 'CTGGAC’
C --> ‘TGACCAA’
T --> ‘GAGACTA’
G --> ‘CTGAAG’

after several cycles lead us to something looking like the real DNA: TGACCAAGAGACTACTGAAGCTGGACCTGGACCTGAAGTGACCAAGAGACTACTGAAGCTGAAG
CTGGACTGACCAATGACCAAGAGACTACTGAAGCTGGACCTGGACCTGAAGTGACCAA...
Taking in account these rules are so direct and simple it is very naive to consider the above sequence as an analog of some natural DNA. However, simulation of the natural polymers with L-grammars seems to have robust perspectives. Two of additional questions when I examine my students (L-systems was a part of my lecture course on the structure of proteins) are: 'Propose an algorithm for reverse engineering of L-systems, i.e. obtain the initial rules from known sequence' and 'Is it possible to perform such a task on DNA molecules? Prove possibility or impossibility'...


Algorithm and interface of the L program (download)

The algorithm is based on the L-grammar described above. There are also a number of symbols that can be involved in the interchange process, but not to be rendered (in this version, at least, thereafter let’s call them as ‘dummy’ symbols). These symbols are: ‘A’, ‘C’, ‘G’, ‘T’, ‘U’, S, K, X. For example, to draw a square one may define the initial clause as ‘U}’and set up the change rule 'U' --> 'F+U'.  The ‘A’, ‘C’, ‘G’, ‘T’, ‘U’ letters are implemented for the purpose of nucleic acids simulation. One exception from the dummy symbols is the letter ‘G’. When occurs in the resulting sequence it will produce a tiny red blossom drawn at the given coordinates. This exception gives an example of how L-grammars could be extended.

The program acquires from the user an initial sequence consisting of valid symbols (both uppercase and lowercase characters are allowed) terminated with the ‘}’ symbol, then the user must type the managing angle, rules of interchange, the desired number of iterations and name of the output file. The data entered is stored both in PLX file (all the rules except the number of iterations) and in PLN file (the whole resulting sequence). When one use PLX file as an input, the number of cycles has to be supplied; if PLN file is used then one need to enter the managing angle.

Interface of this program is very simple. First, you are asked to select whether you’ll enter new rules (Manual mode, press ‘M’) or load them from PLX file (press ‘X’) or load the PLN file (press ‘F’). In the manual mode you are prompted to enter in sequence: initial string (TERMINATED WITH ‘}’), managing angle etc. To enter rules of interchange press the letter you wish to assign rule to; the prompt should appear. Then press RETURN followed by the change rule. When all the rules are supplied press the ESC key, type in the file name you wish, press RETURN once again and wait:

 

After the sequence of symbols is finalized, the program interpretes it on thescreen:

 If you want to make the image more or less complex or change the managing angle restart the program and load the corresponding PLX or PLN file. After you are satisfied with the image, the PLN file can be rendered with my VB script in CorelDRAW 9.0. This script comes together with the zip package.

 

Now you can export L-systems in CorelDRAW!

Installation and use of the VB script.

I recommend to fully incorporate this script into CorelDRAW for easier use. In order to do that follow these steps:

    1. From CorelDRAW open the file l.cdr provided. When asked about macros answer “Enable macros” (there are no viruses, trust me).
    2. Run menu Tools/VisualBasic/VisualBasic Editor or press Alt-F11.
    3. In the Object browser drag’n’drop the module ‘lgramm’ from the modules of l.cdr to the global modules. Do the same with ‘lgf1’ and ‘lhelp’ forms of l.cdr.
    4. Run menu Tools/Options; select Customize/Toolbars/VBA Macros/lgramm.main. Then drag’n’drop the desired icon from the right to one of the toolbars.

That’s all. You can run the script by pressing this button. If you don’t wish to integrate this script, it can be started only when l.cdr is opened via menu Tools/VisualBasic/Play by selectin the lgramm.main procedure.

In l.cdr file you’ll find also a 1X1 cm gray locked square with a red blossom as an example in it. This square is the place to store flowers or other stuff that the L-system will draw when it find ‘G’ letter in the sequence. The object in the square must be grouped and has not to overspread (or even touch) the square’s borders. When you create new CDR file intending to use the script you should also mark that area in the same place (it's not obligatory to be a square, you can use guidelines if prefer).

Of course, you can dig into the source code and tune it at will. Below is an example of what you would obtain in CorelDraw when running the script (sakura.pln).

 

References

1. Kislyuk O. S. A Formal System Generating Landscape Paintings in the Monochromatic Style of the Medieval China // Programmirovanie (Programming, in Russian).-1996.- N 2.- P. 53-63.
2. Kislyuk O. S. MORPHO - the Progam to Simulate Development of Geometric Forms of Plants // Programmirovanie (Programming, in Russian).-1995.- N 5.- P. 55-62.
3. Lindenmayer systems: Impact on Theoretical Computer Science, Computer Graphics, and Developmental Biology, G. Rosenberg and A. Salomaa, Eds. Springer-Verlag, Berlin, 1992.
4. Lindenmayer A. Developmental Algorithms for Multicellular Organisms: A Survey of L-systems // J. Theor. Biol.- 1975.- V. 54- P. 3-22.
5. Prusinkiewicz P., Lindenmayer A. The Algorithmic Beauty of Plants. N.-Y. Springer, 1990.

Contacts

 

Please send your questions to: