Bei dieser Aufgabe stellen wir Ihnen ein einfaches Beispiel für eine sogenannte kontextfreie Grammatik vor. Kontextfreie Grammatiken sind wichtig z. B. bei der Beschreibung von Programmiersprachen.

Die Aufgabe: Max entdeckt in seinem Kaktus eine merkwürdige Art Würmer. Sie bestehen aus roten, grünen und weißen Segmenten – Max schreibt die Segmente eines Wurms von vorne (die Würmer haben eine erkennbare Schnauze) nach hinten auf mit den Abkürzungen r (rot), g (grün) und w (weiß), etwa so: rwggr.

Dabei beobachtet er, dass ein Wurm wachsen kann, indem aus einem weißen Segment vorne ein rotes und hinten ein grünes herauswächst, z. B. wächst grgwr zu grgrwgr.
Eine genauere Betrachtung zeigt, dass das Wachstum immer passiert, indem ein weißes Segment durch eine Folge von Segmenten ersetzt wird – das eben beschriebene Wachstum notiert Max als w → rwg und er entdeckt, dass auch noch drei weitere Wachstumsarten vorkommen. Insgesamt sind es folgende:

1.  w → ww
2.  w → rwg
3.  w → gwr
4.  w → gr

Frisch geschlüpfte Würmer bestehen nur aus einem weißen Segment. Bei einem Wurm mit mehreren weißen Segmenten können diese unabhängig voneinander wachsen. Ein Wurm, der kein weißes Segment mehr hat, ist offensichtlich ausgewachsen. Der Wurm rgrggr könnte z. B. so gewachsen sein: w → ww → wgr → rwggr → rgrggr.

Max möchte eine komplette Sammlung aller möglichen Färbungen ausgewachsener Würmer mit genau vier Segmenten.