Editing L-system (section)

==L-system structure==
The [[recursion|recursive]] nature of the L-system rules leads to [[self-similarity]] and thereby, [[fractal]]-like forms are easy to describe with an L-system.   Plant models and natural-looking organic forms are 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''),

where

* '''V''' (the ''alphabet'') is a set of symbols containing both elements that can be replaced (''variables'') and those which cannot be replaced ("constants" or "terminals")
* '''ω''' (''start'', ''axiom'' or ''initiator'') is a string of symbols from '''V''' defining the initial state of the system
* '''P''' is a set of ''[[Production (computer science)|production rule]]s'' 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 which is a member of the set 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'' or ''terminals''. (See [[Law of identity]]).

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. The fact that each iteration employs as many rules as possible differentiates an L-system from a [[formal language]] generated by a [[formal grammar]], which applies only one rule per iteration. If the production rules were to be applied only one at a time, one would quite simply generate a string in a language, and all such sequences of applications would produce the language specified by the grammar.  There are some strings in some languages, however, that cannot be generated if the grammar is treated as an L-system rather than a language specification. For example,<ref>{{cite web |title=L-systems |url=https://encyclopediaofmath.org/index.php?title=L-systems&oldid=47547 |website=Encyclopedia of Mathematics |publisher=Springer |access-date=26 July 2022}}</ref> suppose there is a rule S→SS in a grammar. If productions are done one at a time, then starting from S, we can get first SS, and then, applying the rule again, SSS.  However, if all applicable rules are applied at every step, as in an L-system, then we cannot get this sentential form.  Instead, the first step would give us SS, but the second would apply the rule twice, giving us SSSS. Thus, the set of strings produced by an L-systems from a given grammar is a subset of the formal language defined by the grammar, and if we take a language to be defined as a set of strings, this means that a given L-system is effectively a subset of the formal language defined by the L-system's grammar.

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 a [[context-free 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.