Saturday, 12 March 2011

L-system structure

The recursive nature of the L-system rules leads to self-similarity and thereby fractal-like forms which are easy to describe with an L-system. Plant models and natural-looking organic forms are similarly easy to define, as by increasing the recursion level the form slowly 'grows' and becomes more complex. Lindenmayer systems are also popular in the generation of artificial life.

L-system grammars are very similar to the semi-Thue grammar (see Chomsky hierarchy). L-systems are now commonly known as parametric L systems, defined as a tuple

    G = (V, ω, P),


    * V (the alphabet) is a set of symbols containing elements that can be replaced (variables)
    * ω (start, axiom or initiator) is a string of symbols from V defining the initial state of the system
    * P is a set of production rules or productions defining the way variables can be replaced with combinations of constants and other variables. A production consists of two strings, the predecessor and the successor. For any symbol A in V which does not appear on the left hand side of a production in P, the identity production A → A is assumed; these symbols are called constants.

The rules of the L-system grammar are applied iteratively starting from the initial state. As many rules as possible are applied simultaneously, per iteration; this is the distinguishing feature between an L-system and the formal language generated by a formal grammar. If the production rules were to be applied only one at a time, one would quite simply generate a language, rather than an L-system. Thus, L-systems are strict subsets of languages.

An L-system is context-free if each production rule refers only to an individual symbol and not to its neighbours. Context-free L-systems are thus specified by either a prefix grammar, or a regular grammar. If a rule depends not only on a single symbol but also on its neighbours, it is termed a context-sensitive L-system.

If there is exactly one production for each symbol, then the L-system is said to be deterministic (a deterministic context-free L-system is popularly called a D0L-system). If there are several, and each is chosen with a certain probability during each iteration, then it is a stochastic L-system.

Using L-systems for generating graphical images requires that the symbols in the model refer to elements of a drawing on the computer screen. For example, the program Fractint uses turtle graphics (similar to those in the Logo programming language) to produce screen images. It interprets each constant in an L-system model as a turtle command.

No comments:

Post a Comment