Formal language theory/Parallel replacement systems
Parallel replacement systemsEdit
A foray into the language theoretic aspects of Lindenmayer systems. For D0L systems, we have followed the presentation in Salomaa's book.
A D0L (deterministic, zero context) system over an alphabet consists of a start string and a single replacement rule given by a homomorphism . These systems have perhaps surprising properties.
Question: What happens when for some string ?
0L: instead of a homomorphism, there is a finite 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 of homomorphisms
Question: Find a language that is in DT0L but not in D0L or 0L.
- Arto Salomaa, Jewels in Formal Language Theory, Computer Science Press 1981
- Rozenberg and Salomaa, The Mathematical Theory of L Systems