Formale Systeme

Automaten
Prozesse
Sommersemester 2026

Peter Rossmanith
Fakultät für Informatik, RWTH Aachen

Vorlesungsskript für das Studium der Informatik und verwandter Fachgebiete an der
RWTH Aachen
1. Vorwort

Dieses Skript ist aus den Folien zur Vorlesung und einer fast wortgetreuen Transkripti-
on meines dazu mündlich gehaltenen Vortrags entstanden. Diese Entstehungsgeschichte
erklärt die teilweise informelle Sprache, welche auch dieser überarbeiteten Version noch
anzusehen ist. Ich habe mich bewußt für eine solche Form entschieden, weil ich den Geist
der Vorlesung auch hier noch durchscheinen lassen möchte.
Ich möchte die Gelegenheit nutzen, an dieser Stelle den vielen Personen zu danken, die zur
Erstellung beitrugen. Da sind zunächst die Tutoren und Tutorinnen zu nennen, welche
aus dem Vorlesungsvideo in stundenlanger Arbeit meine gesprochenen Sätze transkribier-
ten und sie zu einem lesbaren Dokument zusammenstellten, welches auch die wichtigen
Verweise auf die zugehörigen Folien enthält. Vielen Dank an Albert, Hendrik, Jonathan,
Marian, Niels, Paul, Sarah, Sebastian, Stefan, Thomas, Tobias und Viktor.
Einen wichtigen Anteil haben auch meine Assistenten, die die Vorlesung allgemein in allen
Aspekten stark unterstützten und auch bei der Erstellung des Skripts eine wichtige Rolle
spielten. Vielen Dank an Jan Dreier, Fabian Emmes, Tim Hartmann, Joachim Kneis,
Alexander Langer, Henri Lotze, Daniel Mock, Daniel Mölle und Stefan Richter.
Das eigentliche Destillieren der relevanten Teile aus der Niederschrift und ihre Umwand-
lung in einen lesbaren Text war die größte Aufgabe und auch mit einem großen zeitlichen
Aufwand verbunden. Ich danke daher besonders Elias Burggraef, Laurenz Grote und Felix
Knispel, die diese Aufgabe mit großem persönlichem Engagement neben ihrem Studium
während des laufenden Semesters leisteten. Zuletzt danke ich der RWTH Aachen und der
Fachgruppe Informatik für die zusätzliche Finanzierung, welche das Erstellen des Skripts
unterstützten.
Heute können wir glücklicherweise den Vorlesungsbetrieb wieder ohne Einschränkungen
durchführen, und die Corona-Krise liegt hoffentlich hinter uns. Dennoch hoffe ich, dass
sich dieses Skript als nützlich erweist. Es enthält nach wie vor den Inhalt der Vorlesung
beinahe wortgetreu, wurde aber weiter bearbeitet und verbessert. Ich wünsche allen Stu-
dentinnen und Studenten viel Spaß bei dieser Vorlesung, welche ein spannendes Thema
der Informatik umfaßt. Insbesondere steht der Inhalt auf festem mathematisch fundier-
tem Boden und stellte sich gleichzeitig als sehr nützlich in der Praxis heraus. Beispiele
von Anwendungen finden sich überall, nicht nur im Compilerbau und im Bereich der for-
malen Verifikation. Es scheint sich ein Programmierstil zu entwickeln, der stark auf das
Verwenden von regulären Ausdrücken setzt, so dass diese nicht verdeckt im Hintergrund,
sondern als deutlich sichtbar in vielen Anwendungsprogrammen und sogar Webseiten auf-
tauchen. Auch die kontextfreien Sprachen sind oft prominent sichtbar, beispielsweise in
der Syntaxbeschreibung von Programmier- und Domainspezifischen Sprachen und nicht
zuletzt durch XML, welches ebenfalls auf diesem Konzept beruht.

Aachen, im April 2023 A.D.

Peter Rossmanith

i
ii
Vorwort zur neuen Version

Diese Version des Skripts wurde nochmals grundlegend überarbeitet. Dabei wurde neues
Material ergänzt, zahlreiche Fehler beseitigt und ein ausführliches Stichwortverzeichnis
hinzugefügt, um die Orientierung im Skript zu erleichtern. Ich hoffe, dass diese Verbes-
serungen das Skript noch nützlicher machen.
Ein herzlicher Dank geht an alle, die durch ihre Mitarbeit zu dieser neuen Version beige-
tragen haben. Die konstruktiven Rückmeldungen der Studierenden waren dabei besonders
wertvoll und haben maßgeblich zur Verbesserung beigetragen.
Ich wünsche Ihnen viel Erfolg und Freude beim Studium der Formalen Sprachen und
Automatentheorie.

Aachen, im April 2026 A.D.

Peter Rossmanith

iii
iv
Inhaltsverzeichnis

1. Vorwort i

Vorwort zur neuen Version iii

1 Einführung 1
1.1 Organisatorisches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Künstliche Pflanzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Empfohlene Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Alphabete, Wörter, Sprachen . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Reguläre Sprachen 15
2.1 Reguläre Ausdrücke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Endliche Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3 Nichtdeterministische endliche Automaten . . . . . . . . . . . . . . . . . 35
2.4 Potenzmengenkonstruktion . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.5 NFA mit epsilon-Übergängen . . . . . . . . . . . . . . . . . . . . . . . . 40
2.6 Minimale DFAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.7 Berechnung des minimalen DFA . . . . . . . . . . . . . . . . . . . . . . . 53
2.8 Vom Automaten zum regulärem Ausdruck . . . . . . . . . . . . . . . . . 57
2.9 Pumping-Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.10 Entscheidungsprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

3 Kontextfreie Sprachen 73
3.1 Kontextfreie Sprachen und Grammatiken . . . . . . . . . . . . . . . . . . 73
3.2 Ableitungsbäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.3 Die pre*-Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.4 Entscheidungsprobleme für CFGs . . . . . . . . . . . . . . . . . . . . . . 95
3.5 Normalformen für CFGs . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
3.6 Chomsky-Normalform . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
3.7 Greibach-Normalform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
3.8 Das Pumping-Lemma für CFLs . . . . . . . . . . . . . . . . . . . . . . . 112
3.9 Kellerautomaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
3.10 Deterministische Kellerautomaten . . . . . . . . . . . . . . . . . . . . . . 124
3.11 Abschlusseigenschaften . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

v
4 Die Chomsky-Hierarchie 137

5 Prozesse 145
5.1 Synchronisierte Produkte von Automaten . . . . . . . . . . . . . . . . . . 145
5.2 Petrinetze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

vi
Kapitel 1

Einführung

Dieses Skript deckt den Stoff der Vorlesung Formale Sprachen, Automaten und Prozesse
ab, welche regelmäßig für das zweite Semester im Studiengang Informatik an der RWTH
Aachen angeboten wird.

1.1 Organisatorisches
Die Vorlesung ist dreistündig, wir haben aber wegen des Vorlesungsrasters vier Stunden in
der Woche zur Verfügung. Während wir diese vier Stunden normalerweise voll ausnutzen,
werden wir am Ende des Semesters früher fertig oder können auch in der Mitte einmal eine
Woche ausfallen lassen. In der vorlesungsfreien Zeit gibt es dann zwei Klausurtermine.
Für die Klausurteilnahme ist eine regelmässige Teilnahme an den Tutorübungen erforder-
lich und mindestens 50% der Punkte in den wöchentlichen Hausaufgaben. Die Übungs-
blätter mit Tutor- und Hausaufgaben werden vor dem Tutoriums zur Verfügung gestellt.
Am Ende jeder Tutorübung gibt es je einen kurzen Minitest zur eigenen Überprüfung
des Wissensstands. Es gibt bis zu 20% Bonuspunkte für die Klausur basierend auf den
bearbeiteten Minitests.
Die Tutorübungen laufen also so ab:

• Ausgabe der Übungsblätter

• Optionale Abgabe der Hausaufgaben, die letzte Woche ausgegeben wurden

• Rückgabe der korrigierten Hausaufgaben vom letzten Mal

• Gemeinsames Bearbeiten der Tutoraufgaben

• Miniprüfung (15 Minuten) am Ende des Tutoriums

Es gibt auch jede Woche eine Globalübung, in welcher ausgewählte Aufgaben vorgerech-
net werden. Diese werden entsprechend der in der Hausaufgabenkorrektur gefundenen
Defiziten und aufgrund von Rückmeldungen aus den Tutorgruppen entworfen. Dort steht
auch viel Zeit für Fragen und Diskussionen zur Verfügung.

1
2 KAPITEL 1. EINFÜHRUNG

1.2 Motivation
Wir fangen unseren Ausflug in die faszinierende Welt der formalen Sprachen mit einem
einfachen, aber nicht vollkommen unrealistischen Beispiel an, welches bereits viele der
wichtigen kommenden Konzepte andeuten kann.
Ich möchte gerne ein Programm schreiben, das als Eingabe einen Text bekommt, welcher
nur aus Nullen und Einsen besteht. Das Programm soll feststellen, ob dieser String eine
bestimmte Eigenschaft hat. Hier ist es eine Eigenschaft, welche aus zwei Teilen besteht.
Die erste Eigenschaft, welche ich verlange, ist: „Ich möchte nicht, dass irgendwo 11 als
Unterwort vorkommt.“ Und die zweite Eigenschaft, die ich ebenfalls fordere, ist: „Wenn
ich diesen Text, der aus Nullen und Einsen besteht, als Binärzahl interpretiere, möchte
ich, dass sie durch 3 teilbar ist.
Hier sind ein paar Beispiele:

1. Das Wort 0101 sollte nicht akzeptiert werden, da die repräsentierte Zahl fünf ist
und daher nicht durch drei teilbar.

2. Das Wort 1001 dagegen sollte akzeptiert werden, da es die Dezimalzahl neun kodiert
und ausserdem 11 nicht als Unterwort enthält.

3. Nun ist 00110 auf jeden Fall zu verwerfen, da es 11 enthält – wir können uns die
Frage nach der Teilbarkeit durch drei sogar sparen.

4. Schließlich sollten wir 0101010 akzeptieren, da es sowohl durch drei teilbar ist, als
auch kein 11 enthält.

Wie können wir ein effizientes Programm entwerfen und implementieren, das diese Auf-
gabe löst? Wie könnte ein Programm vorgehen, um das Problem zu lösen? Erst einmal
die erste Eigenschaft überprüfen und dann erst die zweite? Dieses Vorgehen ist auf jeden
Fall von einem Software-Engineering-Standpunkt zu loben, da ein großes Problem in zwei
kleine, einfachere Probleme zerteilt wird, welche unabhängig voreinander gelöst werden
können.
Die Alternative wäre, beide Eigenschaften gleichzeitig zu testen. Der Vorteil diese Vor-
gehens wäre, dass es schneller sein könnte, was man aber pauschal erst einmal nicht
garantieren kann.
Hier ist jetzt ein Vorschlag für ein Programm, das die Aufgabe tatsächlich löst:

int F [ ] = { 1, 0, 0, 0, 1, 0, 0 };
int delta[ ][2] = {{0, 1}, {3, 6}, {3, 4}, {2, 5}, {0, 6}, {2, 6}, {6, 6}};

int drei _not_11 (char ∗ w )

{
int q = 0;
while(∗w ) q = delta[q][∗w ++ − ’0’];
return F [q];
}
1.2. MOTIVATION 3

Das ist jetzt ein Programm in C. Es ist wahrscheinlich nicht auf den ersten Blick klar, was
das Programm macht und die zweite Frage ist, ob das Programm überhaupt das Richtige
berechnet. Es sieht zwar sehr kryptisch aus, aber es ist immerhin ziemlich kurz.
Schauen wir es uns einmal genauer an: Oben definieren wir zwei Arrays, die nie geändert
werden und statisch initialisiert werden. In ihnen stehen einfach ein paar Zahlen: Ein
eindimensionales Array mit Nullen und Einsen, und noch ein zweidimensionales Array
mit ganzen Zahlen.
Nun schauen wir einmal, was das Programm macht. Das Programm ist in C geschrieben
und benutzt Zeiger (pointer).
Die Eingabe ist ein Array w, welches null-terminiert sein soll. Das heißt, wenn w[i] = 0
hört das ganze Programm auf. Wir fangen an mit q = 0 und schauen dann in der Tabelle
delta nach, wie wir das q zu ändern haben. Das hängt vom alten q ab und vom gelesenen
Zeichen. Was wir am Ende zurückgeben, ist einfach F [q]. Das heißt, wenn q = 0 ist, dann
wird 1 zurückgegeben, bei q = 1 wird 0 zurückgegeben und so weiter.
Dass das Programm korrekt ist, ist vielleicht im Augenblick nicht so leicht zu sehen.
Wir werden sehen, dass die theoretische Grundlage zu diesem Programm ein sogenannter
„endlicher Automat“ ist. Diesen würden wir so zeichnen:

So ein endlicher Automat ist ein sehr einfaches mathematisches Konstrukt. Er hat endlich
viele Zustände und er „ist immer in einem Zustand“. Die Zustände heißen hier q0 , q1 , . . . , q6 ,
also hat der Automat genau sieben Zustände. Der Automat funktioniert so: Er liest
Zeichen und ändert seinen Zustand. Am Anfang ist er im Zustand q0 . Wenn er jetzt zum
Beispiel eine 0 liest, dann bleibt er in q0 . Wenn er hingegen eine 1 liest, dann würde er
nach q1 gehen. Jetzt können wir ein paar Beispiele anschauen:
Fangen wir mit dem Wort 0101 an. Was macht der Automat, wenn er dieses Wort liest?
Er startet in q0 und liest eine 0 und bleibt in q0 . Dann liest er eine 1 und ist somit in q1 .
Dann liest er wieder eine 0 und landet im Zustand q3 . Mit der letzten 1 endet er schließlich
im Zustand q5 .
Nun gibt es manche Zustände, die in der Zeichnung besonders hervorgehoben sind. Das
sind die sogenannten Endzustände. Wenn der Automat in einem Endzustand endet, dann
akzeptiert er das Wort. Das heißt, das Wort 0101 würde nicht akzeptiert werden, da q5
kein Endzustand ist.
Schauen wir uns ein anderes Wort an: 0101010. Wir starten wieder in q0 . Mit dem Wort
erreichen wir am Ende wieder den Zustand q0 .
Es stellt sich heraus, dass dieser Automat tatsächlich das Richtige macht. Wir beweisen
es nicht an dieser Stelle, aber machen es uns ein bisschen plausibel. Zum Beispiel, wenn
man den Zustand q6 erreicht, dann ist man wirklich verloren, denn dort kommt man nie
wieder heraus. Egal in welchen Zustand wir sind, wenn wir zwei Einsen lesen, dann landen
4 KAPITEL 1. EINFÜHRUNG

drei_not_11: lw $3,0($3)
lb $2,0($4) .L2:
beq $2,$0,.L2 lui $4,%hi(F)
move $3,$0 addiu $4,$4,%lo(F)
lui $5,%hi(delta) sll $3,$3,2
addiu $5,$5,%lo(delta) addu $3,$3,$4
.L3: j $31
sll $3,$3,1 lw $2,0($3)
addu $3,$3,$2 delta:
addiu $4,$4,1 .word 0, 1, 3, 6, 3
addiu $3,$3,-48 .word 4, 2, 5, 0, 6
lb $2,0($4) .word 2, 6, 6, 6
sll $3,$3,2 F:
addu $3,$5,$3 .word 1, 0, 0, 0, 1
bne $2,$0,.L3 .word 0, 0

Abbildung 1.1: MIPS-Programm.

wir in q6 . Das sieht schon einmal richtig aus. Die anderen Zustände benötigen wir, um
festzustellen, ob die Zahl auch durch drei teilbar ist.
Der Automat testet also auf diese Weise beide Eigenschaften gleichzeitig. Wir könnten
das auch getrennt behandeln, dann müssten wir aber das Wort zweimal lesen, was für den
Computer viel Arbeit sein kann. Zweimal durch das Wort durchzugehen kann viele Pro-
bleme verursachen. Das Wort ist nach dem ersten Lesen wieder aus dem Cache draußen
und man muss noch einmal alles aus dem Speicher holen, was sehr teuer ist.
Schauen wir uns jetzt noch einmal die Zeichnung des Automaten und den Quelltext des
Programms an, stellen wir fest, dass das Programm tatsächlich den Automaten simuliert.
Wir können uns leicht vorstellen, dass solche Programme aus einer Beschreibung des
Automaten automatisch erzeugt werden können. Wenn das so ist, muss uns aber die
Unlesbarkeit des Programmes nicht mehr stören, denn wir haben ja den Automaten,
welchen wir stattdessen betrachten und analysieren können.
Überlegen wir uns jetzt noch, ob dieses Programm effizient, also schnell ist. Vom Quelltext
her macht es einen guten Eindruck, aber wir sehen noch mehr, wenn wir das in Maschi-
nensprache übersetzte Programm betrachten. In Abbildung 1.1 sehen wir das für einen
MIPS-Prozessor übersetzte Programm. Dies ist ein typischer RISC-Prozessor, dessen As-
semblercode sehr schön lesbar ist, was für uns einen Vorteil über die weiter verbreitete
Intel-x86-Architektur darstellt.
Schauen wir uns einmal das Maschinenspracheprogramm genauer an. Die innere Schleife
ist zwischen .L3 und .L2 und besteht aus neun Instruktionen. Ein guter Prozessor sollte
eine Instruktion pro Taktzyklus schaffen. Wie viele Verzweigungsinstruktionen führt er
pro Zeichen, welches er liest, aus? Nur eine! Bedingte Verzweigungsinstruktionen sind
immer Gift für moderne Prozessoren, also sind wenige Verzweigungen immer gut und
wir haben hier nur eine Verzweigung pro gelesenem Zeichen. Dies könnte man mit „loop
unrolling“ noch verbessern, was aber in dieser Situation wahrscheinlich mehr Nach- als
Vorteile hätte.
Da moderne Prozessoren über eine „branch prediction“ verfügen und diese hier praktisch
immer die richtige Vorhersage macht, wird der negative Einfluß der einen Verzweigungs-
1.3. KÜNSTLICHE PFLANZEN 5

operation zusätzlich noch relativiert.

1.3 Künstliche Pflanzen

Wir möchten gerne eine Pflanze zeichnen. Dazu steht uns bereits ein Zeichenprogramm
zur Verfügung, welches einfache Befehle ausführen kann, die es in Form eines Befehlswor-
tes bekommt.
Die einzelnen Befehle sind diese:

F Zeichne eine kurze Linie.

+ Drehe dich ein wenig nach rechts.

- Drehe dich ein wenig nach links.

[ Merke dir die augenblickliche Position und Richtung.

] Kehre zur letzten gemerkten Position und Richtung zurück.

Durch eine Zeichenkette, wie zum Beispiel,

F[+FF][–F]F[+F[+FF][–F]FF[+FF][–F]F][–F[+FF][–F]F]F[+FF][–F]F
wird dann folgende Zeichnung erzeugt:

Ein längeres Kommando, wie zum Beispiel

F[+FF][–F]F[+F[+FF][–F]FF[+FF][–F]F][–F[+FF][–F]F]F[+FF][–F]F[+F[+FF][–F
]F[+F[+FF][–F]FF[+FF][–F]F][–F[+FF][–F]F]F[+FF][–F]FF[+FF][–F]F[+F[+FF][-
-F]FF[+FF][–F]F][–F[+FF][–F]F]F[+FF][–F]F][–F[+FF][–F]F[+F[+FF][–F]FF[+F
F][–F]F][–F[+FF][–F]F]F[+FF][–F]F]F[+FF][–F]F[+F[+FF][–F]FF[+FF][–F]F][-
-F[+FF][–F]F]F[+FF][–F]F[+F[+FF][–F]F[+F[+FF][–F]FF[+FF][–F]F][–F[+FF][–
F]F]F[+FF][–F]F[+F[+FF][–F]F[+F[+FF][–F]FF[+FF][–F]F][–F[+FF][–F]F]F[+FF]
[–F]FF[+FF][–F]F[+F[+FF][–F]FF[+FF][–F]F][–F[+FF][–F]F]F[+FF][–F]F][–F[
+FF][–F]F[+F[+FF][–F]FF[+FF][–F]F][–F[+FF][–F]F]F[+FF][–F]F]F[+FF][–F]F[
+F[+FF][–F]FF[+FF][–F]F][–F[+FF][–F]F]F[+FF][–F]FF[+FF][–F]F[+F[+FF][–F]
FF[+FF][–F]F][–F[+FF][–F]F]F[+FF][–F]F[+F[+FF][–F]F[+F[+FF][–F]FF[+FF][–
F]F][–F[+FF][–F]F]F[+FF][–F]FF[+FF][–F]F[+F[+FF][–F]FF[+FF][–F]F][–F[+FF
][–F]F]F[+FF][–F]F][–F[+FF][–F]F[+F[+FF][–F]FF[+FF][–F]F][–F[+FF][–F]F]
F[+FF][–F]F]F[+FF][–F]F[+F[+FF][–F]FF[+FF][–F]F][–F[+FF][–F]F]F[+FF][–F]
F][–F[+FF][–F]F[+F[+FF][–F]FF[+FF][–F]F][–F[+FF][–F]F]F[+FF][–F]F[+F[+FF
][–F]F[+F[+FF][–F]FF[+FF][–F]F][–F[+FF][–F]F]F[+FF][–F]FF[+FF][–F]F[+F[+
FF][–F]FF[+FF][–F]F][–F[+FF][–F]F]F[+FF][–F]F][–F[+FF][–F]F[+F[+FF][–F]
6 KAPITEL 1. EINFÜHRUNG

FF[+FF][–F]F][–F[+FF][–F]F]F[+FF][–F]F]F[+FF][–F]F[+F[+FF][–F]FF[+FF][–F
]F][–F[+FF][–F]F]F[+FF][–F]F]F[+FF][–F]F[+F[+FF][–F]FF[+FF][–F]F][–F[+FF
][–F]F]F[+FF][–F]F[+F[+FF][–F]F[+F[+FF][–F]FF[+FF][–F]F][–F[+FF][–F]F]F[
+FF][–F]FF[+FF][–F]F[+F[+FF][–F]FF[+FF][–F]F][–F[+FF][–F]F]F[+FF][–F]F][
–F[+FF][–F]F[+F[+FF][–F]FF[+FF][–F]F][–F[+FF][–F]F]F[+FF][–F]F]F[+FF][–
F]F[+F[+FF][–F]FF[+FF][–F]F][–F[+FF][–F]F]F[+FF][–F]F
kann schon eine recht realistisch aussehende Pflanze hervorbringen:

Wie man ein solches Zeichenprogramm erstellt interessiert uns jetzt nicht, sondern eher,
wie man die Befehlssequenz erstellt. Ist das schwer? Man muss sich bloß in eine Pflanze
gedanklich hineinversetzen und das Problem wird ganz einfach.
Wir fangen mit einem einzelnen F an. Dann nehmen wir das F und ersetzen es durch den
kurzen String (F → F [+F F ][− − F ]F ). Dann ersetzen wir wieder in diesem String alle
F durch den neuen String und so weiter. Wir wiederholen dies einige Male, aber nicht
zu oft. Wie man leicht sieht, wächst die Länge der Zeichenkette exponentiell, ähnlich wie
die Ansteckungswelle einer Epidemie.
Warum funktioniert das? Stellen wir uns ein kleines Stück in dieser Pflanze vor, welches
wächst. Das kann irgendwo in der Mitte der Pflanze sein. Das Stück wird immer länger
und irgendwann ist so viel Platz vorhanden, dass es genug Sonnenlicht bekommt, um die
Kraft für einen Seitentrieb zu haben. Dieser entsprießt dieser Stelle mit einem bestimmten
Winkel. Wir müssen diesen biologischen Prozess jetzt nur noch simulieren.
Abbildung 1.2 zeigt ein paar Pflanzen, die auf diese Art entstanden sind und ganz
hübsch aussehen. Während die Zeichnungen selbst erstellt sind, stammen die zugrun-
deliegenden Grammatiken aus einem Buch, welches netterweise frei zugänglich ist: http:
//[Link]/papers/abop/[Link].
Die Abbildungen, welche durch iterierte Anwendungen die Kommandosequenzen für den
Pflanzenzeichner generieren, werden wir später Homomorphismen über Wörtern nennen.
Man kann sich leicht denken, dass man die Kommandosprache erweitern kann, um noch
andere Pflanzenarten realistisch darstellen zu können. Dies ist in der Tat der Fall. Zum
Beispiel kann ein neues Kommando verlangen, dass sich die Zeichenschrittweite fürderhin
um eine gewissen Faktor verkürzt. Dies kann simulieren, dass die Pflanze zu den Blät-
tern hin schwächer wird oder dass sich der Durchmesser der Triebe verkleinert. Ebenso
1.3. KÜNSTLICHE PFLANZEN 7

Abbildung 1.2: Einige künstliche Pflanzen.

8 KAPITEL 1. EINFÜHRUNG

Abbildung 1.3: Weitere künstliche Pflanzen.

kann man das Wachsen von Blättern oder Früchten simulieren oder mehrere Winkel ein-
führen, um dreidimensionale Strukturen zu erzeugen, die dann künstliche Landschaften
in 3D-Spielen ausfüllen können. Verwendet man zusätzlich ein „Verkürzungskommando“
bekommt man Bilder wie in Abbildung 1.3.

1.4 Empfohlene Literatur

Die folgenden Bücher sind alle schon etwas alt, aber sehr gut. Teilweise könnte man
argumentieren, dass sogar die älteren Versionen in vielerlei Hinsicht besser sind. Das
wichtigste Buch für uns ist das dritte in der Liste.

Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques,
and Tools. Addison-Wesley series in computer science / World student series edition.
Addison-Wesley, 1986. ISBN 0-201-10088-6. URL [Link]
12285707.

Michael A. Harrison. Introduction to Formal Language Theory. Addison-Wesley, 1978.

ISBN 0-201-02955-3.
1.5. ALPHABETE, WÖRTER, SPRACHEN 9

! != % & && ( ) ∗ ∗= + ++ += , − −− −= −> . /

/ = : ; < <= = == > >= ? IDENT NUMBER [ ] ˆ and-assign
auto break case char const continue default do double ellipsis else enum
extern float for goto if int left-assign left-op long mod-assign or-assign
register return right-assign right-op short signed sizeof static string-literal
struct switch typedef union unsigned void volatile while xor-assign { | ||
} ˜

Tabelle 1.1: Tokens für die Programmiersprache C sind auch ein Alphabet, das natürlich
eine wichtige Rolle in einem C-Compiler spielt.

John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to automa-

ta theory, languages, and computation, 3rd Edition. Pearson international edition.
Addison-Wesley, 2007. ISBN 978-0-321-47617-3.

1.5 Alphabete, Wörter, Sprachen

Definition 1.1. Ein Alphabet ist eine endliche Menge von Symbolen.

Beispiele:

• Kleinbuchstaben {a, . . . , z}

• Boole’sche Werte B = {0, 1}

• ASCII, der American Standard Code for Information Interchange.

Die folgende Tabelle zeigt nur die druckbaren Zeichen:

30 40 50 60 70 80 90 100 110 120

0 ( 2 < F P Z d n x
1 ) 3 = G Q [ e o y
2 * 4 > H R \ f p z
3 ! + 5 ? I S ] g q {
4 " , 6 @ J T ^ h r |
5 # - 7 A K U _ i s }
6 $ . 8 B L V ‘ j t ~
7 % / 9 C M W a k u
8 0 : D N X b l v
9 ’ 1 ; E O Y c m w

• Unicode

Alphabete müssen nicht ungedingt Alphabete für natürliche oder Programmiersprachen

sein. Sehen wir uns zwei Beispiele an, die nicht zu diesen Kategorien gehören. Ein Com-
piler liest ein Programm, welches ASCII als Alphabet verwendet. In einer ersten Phase,
der lexikalischen Analyse, wird es in eine Sequenz von Tokens verwandelt. Die Token, die
10 KAPITEL 1. EINFÜHRUNG

in der Programmiersprache C verwendet werden, sind in Tabelle 1.1 aufgelistet. Dabei

handelt es sich einerseits um die in C reservierten Schlüsselwörter, verschiedene Operato-
ren, Klammersymbole etc. und die beiden Tokens IDENT und NUMBER, die Bezeichner
und Zahlen repräsentieren. Das C Programm

int main(int argc, char *argv[]) { return 0; }

wird in folgende Token-Sequenz verwandelt:

int IDENT ( IDENT , char ∗ IDENT [ ] ) { return NUMBER ; }.

Dieses „Wort“ aus Tokens ist dann die Eingabe für die nächste Phase der Programmüber-
setzung, die syntaktische Analyse. In der syntaktischen Analyse wird ein Syntaxbaum
konstruiert, dessen Blätter die Tokens aus der Eingabe sind.
Informell können wir Wörter und Sprachen so definieren:

1. Ein Wort ist eine Aneinanderkettung von Symbolen aus einem Alphabet.

2. Eine Sprache ist eine Menge von Wörtern.

Während der Begriff der Sprache auf diese Weise einigermaßen sauber definiert ist, trifft
dies auf das Wort sicherlich nicht zu.
Wie sieht also eine formale, mathematisch korrekte Formalisierung dieser Begriffe aus? Ist
es überhaupt notwendig, diese Begriffe mathematisch zu definieren, obwohl wir intuitiv
genau wissen, was mit ihnen gemeint ist?
Für rigorose Beweisführungen ist eine saubere Definition in der Tat unerläßlich, wie sich
beispielsweise beim mathematischen Zahlbegriff zeigte. Was ist denn eine natürliche Zahl?
Es gibt verschiedene Möglichkeiten diese zu definieren. Die axiomatische Methode ver-
wendet die Peano-Axiome:

1. 1 ist eine natürliche Zahl.

2. Jede natürliche Zahl hat einen Nachfolger (der eine natürliche Zahl ist).

3. Verschiedene natürliche Zahlen haben verschiedene Nachfolger.

4. 1 ist nicht Nachfolger einer natürlichen Zahl.

5. Wenn die 1 eine Eigenschaft besitzt und aus dem Besitz dieser Eigenschaft stets
folgt, dass ihr Nachfolger sie ebenso besitzt, dann haben alle natürliche Zahlen diese
Eigenschaft.

Natürliche Zahlen lassen sich aber auch konstruktiv einführen, indem wir 1 := ∅ definieren
und festlegen, dass 1 eine natürliche Zahl ist und dass falls x eine natürliche Zahl ist, auch
{x, {x}} eine natürliche Zahl ist. Mit dieser Definition ist y genau dann der Nachfolger
von x, wenn x ∈ y. Allerdings hat diese Definition einen kleinen Fehler, welcher zeigt,
dass wir mit Definitionen sehr sorgfältig umgehen müssen: Eines der Peano-Axiome wird
von den eben definierten Zahlen verletzt.
Wir werden axiomatisch vorgehen und auf diese Weise die Begriffe Wörter und Sprache
sauber einführen.
Definition 1.2 (Halbgruppe, Monoid, Erzeugendensystem).
1.5. ALPHABETE, WÖRTER, SPRACHEN 11

1. Eine Halbgruppe (H, ◦) besteht aus einer Menge H und einer assoziativen Verk-
nüpfung ◦ : H × H → H.

2. Ein Monoid ist eine Halbgruppe mit einem neutralen Element.

3. Sei (M, ◦) ein Monoid und E ⊆ M .

E ist ein Erzeugendensystem von (M, ◦), falls jedes m ∈ M als e1 ◦ · · · ◦ en mit
ei ∈ E dargestellt werden kann.

Oft wird (M, ◦, e) anstatt (M, ◦) für ein Monoid geschrieben, wobei e das neutrale Element
ist. Wir werden die kürzere Schreibweise gebrauchen, was dadurch gerechtfertigt ist, dass
das neutrale Element eines Monoids stets eindeutig ist.

Satz 1.1 (Eindeutigkeit des neutralen Elements). Es sei (H, ◦) eine Halbgruppe, die
neutrale Elemente e1 und e2 besitzt. Dann ist e1 = e2 .

Beweis. Da e2 rechtsneutral ist, ist e1 ◦ e2 = e1 . Andererseits ist aber e1 ◦ e2 = e2 , weil e1

linksneutral ist.

Aufgabe 1.1.

1. Eine Halbgruppe besitze ein links- und ein rechtsneutrales Element. Sind beide
notwendigerweise gleich?

2. Eine Halbgruppe besitze zwei linksneutrale Elemente. Sind beide notwendigerweise

gleich?

Beispiel 1.1. (Z, +) ist ein Monoid, {−1, 1} ist ein Erzeugendensystem.

Definition 1.3 (Freies Erzeugendensystem). Ein Erzeugendensystem E für ein Monoid

(M, ◦) ist frei, falls jedes m ∈ M auf nur eine Art als m = e1 ◦ · · · ◦ en mit ei ∈ E
dargestellt werden kann.
Falls E ein freies Erzeugendensystem für (M, ◦) ist, dann sagen wir, dass (M, ◦) das von
E frei erzeugte Monoid ist.

Beispiel 1.2. (Z, +) ist von {−1, 1} nicht frei erzeugt:

• 2 = 1 + 1 = 1 + 1 + (−1) + 1

• 0 = (−1) + 1 = 1 + (−1)

Definition 1.4 (Monoidisomorphismus). Zwei Monoide (M1 , •) und (M2 , ◦) sind iso-
morph, falls es eine Abbildung h : M1 → M2 gibt mit

1. h ist bijektiv.

2. h ist ein Homomorphismus, d.h. h(u • v) = h(u) ◦ h(v) für alle u, v ∈ M1 .

Sind zwei Monoide isomorph, dann sind sie eigentlich (bis auf Umbennenung der Elemen-
te) gleich. Der Isomorphismus ist dabei die Funktion, die die Elemente umbenennt.