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

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

Question: What happens when ${\displaystyle h(w)=wx}$  for some string ${\displaystyle 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 ${\displaystyle H=\{h_{1},\dots ,h_{k}\}}$  of homomorphisms

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