View source for Formal language theory/Parallel replacement systems

==Parallel replacement systems==

A foray into the language theoretic aspects of Lindenmayer systems. For D0L systems, we have followed the presentation in Salomaa's book<ref name="Salomaa">Arto Salomaa, Jewels in Formal Language Theory, Computer Science Press 1981</ref>.

A '''D0L''' (deterministic, zero context) system <math>(\Sigma, h, w)</math> over an alphabet <math>\Sigma</math> consists of a start string <math>w \in \Sigma^{*}</math> and a single replacement rule given by a [[Formal_language_theory/Homomorphisms| homomorphism]] <math>h</math>. These systems have perhaps surprising properties.

Question: What happens when <math>h(w) = wx</math> for some string <math>x</math>?

<!-- Question: do the D0L languages have any interesting closure properties? -->

==Hierachies==

''0L'': instead of a homomorphism, there is a finite [[Formal_language_theory/Homomorphisms|substitution]]

Question: Find a language that is in 0L but not in D0L. (this is not hard)

'''DTOL''': instead of a single homomorphism, there is a ''table'' <math>H=\{h_1, \dots, h_k\}</math> of homomorphisms

Question: Find a language that is in DT0L but not in D0L or 0L.
<!-- answer in R+S -->

<!--
{{AB
    | Question = Question goes here
    | Atext = A text goes here
}} -->

==Further Reading==
===Books===
<!-- Alessandra Carbone, Stephen Semmes, A Graphic Apology for Symmetry and Implicitness, p. 53: interesting connection between finite automata and D0L systems -->
<ref>Rozenberg and Salomaa, The Mathematical Theory of L Systems</ref>
<references/>