Lindenmayer systems, or L-systems for short, are a variant of general rewriting systems. Like a rewriting system, an L-system is also a language generator, where words are generated by applications of finite numbers of rewriting steps to some initial word given in advance. However, unlike a rewriting system, rewriting occurs in parallel in an L-system. The notion of L-system was introduced by plant biologist Aristid Lindenmayer when he was studying the growth development of red algae.
Formally, an L-system is a triple , where
is an alphabet,
is a word over , and
is a finite subset of such that for every , there is at least one such that .
is called the start word, or the axiom of , and elements of are called productions of the L-system , and are written instead of .
As stated above, an L-system is a language generator, where words are generated from the axiom by repeated applications of productions of . Let us see how this is done. Define a binary relation on as follows: for words ,
iff either and , where , or .
Now, take the transitive closure of and set
Then is called the language generated by the L-system . An L-language is for some L-system .
Let . In two derivations, we get . It is easy to see that after derivations, we get , and that . Note that if parallel rewriting is not required then may be derived in three steps: .
Let . Then .
Let . Then .
L-systems can be used to generate graphs. Usually, symbols in represent instructions on how to construct the graph. For example,
generates the famous Koch curve. If is derived from in steps, then represents the -th iteration of the Koch curve. To draw the -th iteration based on , we do the following:
write , where (it is easy to see that ).
at each , a current position , and current direction , are given.
upon reading , where :
if , set and ,
if , set and ,
if , draw a line segment of unit length from to a point based on , and set and .
A production is said to correspond to if . Both productions in Example 2 correspond to . A production is said to be a constant production if it has the form . A symbol in is called a constant if the only corresponding production is the constant production. In the last example above, are both constants. is not a constant in Example 2, even though it has a corresponding constant production.
Given an L-system , we can associate a function as follows: for each , set
Then extends to a substitution . It is easy to see that is just the set of words derivable from in one step: . In fact,
where , and .
Every L-language is context-free.
If an L-system contains a constant production for each symbol in , then is context-free.
An L-system is said to be deterministic if every symbol in has at most one (hence exactly one) production corresponding to it. A deterministic L-system is also called a DL-system. Examples 1,4,5 above are DL-systems. For a DL-system, the associated substitution is a homomorphism, which means that for each , the set is a singleton, so we get a unique sequence of words , such that . If for some , then the word sequence is infinite. In particular, if is a prefix of for all large enough , and the lengths of the words have the property that implies for some , then the DL-system defines a unique infinite word (by taking the union of all finite words). In Example 4 above, the infinite word we obtain is the famous Thue-Morse sequence (an infinite word is an infinite sequence).
An L-system is said to be propagating if no productions are of the form . A propagating L-system is also called a PL-system. All examples above, except 3, are propagating. A DPL-system is a deterministic propagating L-system. In a DPL-system, the lengths of the words in the corresponding sequence are non-decreasing, and one may classify DPL-systems by how fast these lengths grow.
There are also ways one can extend the generative capacity of an L-system by generalizing some or all of the criteria defining an L-system. Below are some:
Create a partition of , the set of non-terminals and the set of terminals, so that only terminal words are allowed in . Such a system is called an EL-system. Formally, an EL-system is a 4-tuple
such that is an L-system, and .
Notice that the productions in an L-system are context-free in the sense that during a rewriting step, the rewriting of a symbol does not depend on the “context” of the symbol (its neighboring symbols). This is the reason why an L-system is also known as a 0L-system. We can generalize an 0L-system by permitting context-sensitivity in the productions. If the rewriting of a symbol depends both on its left and right neighboring symbols, the resulting system is called a 2L-system. On the other hand, a 1L-system is a system such that dependency is one-sided.
Formally, a 2L-system is a quadruple
Both and are defined as in an L-system. is a symbol not in , denoting a blank space. is a subset of , where , such that for every , there is a such that . Elements of are called productions, and are written instead of . Rewriting works as follows: the binary relation on called a rewriting step, is given by iff either , or and , such that
where , and
If , then productions of the second form above do not apply. If , then are the only productions.
A 1L-system is then a 2L-system such that either, for some implies for all , or for some implies for all .
It is easy to see that an L-system is a 2L-system such that if for some , then for all .
Allow the possibility that not all of the symbols may be rewritten. This means that iff either , or and , and either or .
Allow more than one axiom. In other words, the single axiom word is replaced by a set of axioms.
- 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
|Date of creation||2013-03-22 18:57:31|
|Last modified on||2013-03-22 18:57:31|
|Last modified by||CWoo (3771)|