“L-system”的概念、定义、翻译、参考文献-科学参考

L-system

Computer

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
$\begin{array}{l} A \to A B \\ B \to A \end{array}$
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)) \dots$
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.

单词	L-system
释义	L-system Computer 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 $\begin{array}{l} A \to A B \\ B \to A \end{array}$ 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)) \dots$ 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.
随便看	plesiosaurs pleura pleural pleuron plex Plexiglas display screen plexus PL/I plicate Pliensbachian Plinian eruption plinian eruption plinthic horizon plinthite plinthosols Pliny (23–79) Pliny (61–112) Pliocene PLL PL/M PLM PLO plot Plotinus (205–70) Plotinus (c.ad 205–70)