L-system
L-system (Lindenmeyer system) A way of generating infinite sets of strings. L-systems are similar to grammars with the crucial difference that, whereas for grammars each step of derivation rewrites a single occurrence of a nonterminal, in an L-system all nonterminals are rewritten simultaneously. An L-system is therefore also known as a kind of parallel rewriting system. L-systems were first defined in 1968 by A. Lindenmeyer as a way of formalizing ways in which biological systems develop. They now form an important part of formal language theory.
The subject has given rise to a large number of different classes of L-systems. The simplest are the DOL systems, in which all symbols are nonterminals and each has a single production. For example, with productions A → AB B → A
one derives starting from A the sequence
A AB ABA ABAAB ABAABABA …
This is called the sequence of the DOL-system, while the set of strings in the sequence is called the language. The growth-function gives the length of the ith string in the sequence; in the example this is the Fibonacci function.
Note that the productions define a homomorphism from {A,B}* to itself. A DOL-system consists therefore of an alphabet Σ, a homomorphism h on Σ*, and an initial Σ-word w. The sequence is then w h(w) h(h(w)) …
The letter D in DOL stands for deterministic, i.e. each symbol has just one production. An OL-system can have many productions for each symbol, and is thus a substitution rather than a homomorphism. Other classes are similarly indicated by the presence of various letters in the name: T means many homomorphisms (or many substitutions); E means that some symbols are terminals; P means that no symbol can be rewritten to the empty string; an integer n in place of O means context-sensitivity – the rewriting of each symbol is dependent on the n symbols immediately to the left of it in the string.
The subject has given rise to a large number of different classes of L-systems. The simplest are the DOL systems, in which all symbols are nonterminals and each has a single production. For example, with productions A → AB B → A
one derives starting from A the sequence
A AB ABA ABAAB ABAABABA …
This is called the sequence of the DOL-system, while the set of strings in the sequence is called the language. The growth-function gives the length of the ith string in the sequence; in the example this is the Fibonacci function.
Note that the productions define a homomorphism from {A,B}* to itself. A DOL-system consists therefore of an alphabet Σ, a homomorphism h on Σ*, and an initial Σ-word w. The sequence is then w h(w) h(h(w)) …
The letter D in DOL stands for deterministic, i.e. each symbol has just one production. An OL-system can have many productions for each symbol, and is thus a substitution rather than a homomorphism. Other classes are similarly indicated by the presence of various letters in the name: T means many homomorphisms (or many substitutions); E means that some symbols are terminals; P means that no symbol can be rewritten to the empty string; an integer n in place of O means context-sensitivity – the rewriting of each symbol is dependent on the n symbols immediately to the left of it in the string.
More From encyclopedia.com
System , sys·tem / ˈsistəm/ • n. 1. a set of connected things or parts forming a complex whole, in particular: ∎ a set of things working together as parts of… Systems Design , A system can be defined in several ways, including: (1) a set of interrelated parts that function as a whole to achieve a common purpose; (2) a piece… Signs And Symbols , Symbols
Culture is based on symbols. Flags, traffic lights, diplomas, and mathematical notation are all, in their various ways, symbols. So foundatio… Symbol , Symbol
From a psychoanalytic perspective, the symbol refers to all indirect and figurative representations of unconscious desire (symptoms, dreams, s… Systems Analysis , During the normal course of doing business, companies engaging in e-commerce are faced with a wide variety of challenges or problems. These vary depe… Sympathetic Nervous System , sympathetic nervous system That part of the autonomic nervous system which generally acts to stimulate the body to cope with stress, such as increasi…
You Might Also Like
NEARBY TERMS
L-system