Graftal

related topics
{math, number, function}
{company, market, business}
{specie, animal, plant}
{language, word, form}
{mi², represent, 1st}

A graftal or L-system is a formal grammar used in computer graphics to recursively define branching tree and plant shapes in a compact format. The shape is defined by a string of symbols constructed by a graftal grammar. A graftal grammar consists of an alphabet of symbols that can be used in the strings, a set of production rules which translate each symbol into a non-empty string of symbols, and an axiom from which to begin construction.

Contents

Example

  • axiom:
    • 0
  • rules:
    • 1 → 11
    • 0 → 1[0]0
    • [ → [
    • ] → ]

The graftal is built by recursively feeding the axiom through the production rules. Each character of the input string is checked against the rule list to determine which character or string to replace it with in the output string. In this example, a '1' in the input string becomes '11' in the output string, while '[' remains the same. Applying this to the axiom of '0', we get:

We can see that this string quickly grows in size and complexity. This string can be drawn as an image by using turtle graphics, where each symbol is assigned a graphical operation for the turtle to perform. For example, in the sample above, the turtle may be given the following instructions:

  • 0: draw a line segment ending in a leaf
  • 1: draw a line segment
  • [: push position and angle, turn left 45 degrees
  • ]: pop position and angle, turn right 45 degrees

The push and pop refer to a LIFO stack (more technical grammar would have separate symbols for "push position" and "turn left"). When the turtle interpretation encounters a '[', the current position and angle are saved, and are then restored when the interpretation encounters a ']'. If multiple values have been "pushed," then a "pop" restores the most recently saved values. Applying the graphical rules listed above to our earlier recursion, we get:

Variations

A number of elaborations on this basic graftal technique have been developed which can be used in conjunction with each other. Among these are stochastic, context sensitive, and parametric grammars.

Stochastic grammars

The grammar model we have discussed thus far has been deterministic—that is, given any symbol in the grammar's alphabet, there has been exactly one production rule, which is always chosen, and always performs the same conversion. One alternative is to specify more than one production rule for a symbol, giving each a probability of occurring. For example, in the above grammar, we could change the rule for rewriting "0" from:

To a probabilistic rule:

Under this production, whenever a "0" is encountered during string rewriting, there would be a 50% chance it would behave as previously described, and a 50% chance it would not change during production. When a stochastic grammar is used in an evolutionary context, it is advisable to incorporate a random seed into the genotype, so that the stochastic properties of the image remain constant between generations.

Full article ▸

related documents
Borel algebra
Automata theory
Least common multiple
Special linear group
Golden ratio base
Quasigroup
Operator overloading
Linear subspace
Cotangent space
Column space
Monotone convergence theorem
Theory of computation
Product topology
Spectrum of a ring
Generating trigonometric tables
Mean value theorem
De Morgan's laws
Associative algebra
Discriminant
Measure (mathematics)
1 (number)
Stirling's approximation
Cauchy-Riemann equations
Sylow theorems
NaN
Isomorphism theorem
Jacobi symbol
Diffeomorphism
Differential topology
Tree (data structure)