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.

A D0L (deterministic, zero context) system $(\mathrm{\Sigma },h,w)$ over an alphabet $\mathrm{\Sigma }$ consists of a start string $w\in {\mathrm{\Sigma }}^{*}$ and a single replacement rule given by a homomorphism $h$. These systems have perhaps surprising properties.

Question: What happens when $h(w)=wx$ for some string $x$?

Hierachies

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 $H=\{h_1,\dots ,h_k\}$ of homomorphisms

Question: Find a language that is in DT0L but not in D0L or 0L.