# 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 ?

## HierachiesEdit

*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

### BooksEdit

^{[2]}