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[1].

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.

Further ReadingEdit



  1. Arto Salomaa, Jewels in Formal Language Theory, Computer Science Press 1981
  2. Rozenberg and Salomaa, The Mathematical Theory of L Systems