working backward. This cannot be taken too literally, since it is not clear what to
do with the last production. But the observation does provide a starting point for
a proof of the following theorem that characterizes the power of Markov
algorithms.
Theorem 13.7
A language is recursively enumerable if and only if there exists a Markov
algorithm for it.
Proof: See Salomaa (1985, p. 35).
L-Systems
The origins of L-systems are quite different from what we might expect. Their
developer, A. Lindenmayer, used them to model the growth pattern of certain
organisms. L-systems are essentially parallel rewriting systems. By this we
mean that in each step of a derivation, every symbol has to be rewritten. For this
to make sense, the productions of an L-system must be of the form
where a ∈ Σ and u ∈ Σ*. When a string is rewritten, one such production must
be applied to every symbol of the string before the new string is generated.
Example 13.10
Let Σ = {a} and
a → aa
define an L-system. Starting from the string a, we can make the derivation
a ⇒ aa ⇒ aaaa ⇒ aaaaaaaa.
The set of strings so derived is clearly