Institut für Formale Methoden der Informatik
Universität Stuttgart
Universitätsstraße 38
D–70569 Stuttgart
Bachelorarbeit Nr. 64
Eine Algebraische Konstruktion
für den Kleene-Stern regulärer
Sprachen
Andreas Bühler
Studiengang: Informatik
Prüfer/in: Prof. Dr. Volker Diekert
Betreuer/in: Dr. Manfred Kufleitner
Begonnen am: 17. Mai 2013
Beendet am: 16. November 2013
CR-Nummer: F.4.3

Kurzfassung
In dieser Bachelorarbeit werden zwei Monoidkonstruktionen vorgestellt, die, auf Basis eines
erkennenden Monoids einer Sprache, den Kleene-Stern dieser Sprache erkennen. Die erste
Konstruktion basiert nur auf dem erkennenden Monoid der Sprache, während die zweite
Konstruktion zusätzlich dazu auch auf der erkennenden Menge in dem Monoid basiert.
3

Inhaltsverzeichnis
1 Einleitung 7
2 Allgemeine Sternkonstruktion 9
3 Spezielle Sternkonstruktion 13
4 Zusammenfassung und Ausblick 19
Literaturverzeichnis 21
5

1 Einleitung
Von allen Operation die in regulären Ausdrücken vorkommen, ist der Kleene-Stern am schwie-
rigsten zu erfassen. Das liegt unter anderem daran, dass L∗ mehr oder weniger komplex
als L sein kann. Beispielsweise ist für L = {ak | k ungerade} das dazugehörende L∗ = {a}+.
Damit ist L∗ einfacher zu erfassen als L selbst. Für viele andere Sprachen ist das Resultat des
Kleene-Sterns dieser Sprache allerdings schwieriger nachzuvollziehen. Die Sternhöhe eines
regulären Ausdrucks wurde von L.C. Eggan in [Egg63] als die größte Anzahl verschachtelter
Kleene-Sterne in diesem Ausdruck definiert. Die Sternhöhe einer regulären Sprache entspricht
dann dem Minimum der Sternhöhen aller regulären Ausdrücke für diese Sprache.
Für diese Sternhöhe ist die Unterscheidung zwischen Sprachen der Sternhöhe 0 und denen
mit Sternhöhe größer 0 einfach: Sprachen mit Sternhöhe 0 sind endlich, und alle endlichen
Sprachen haben Sternhöhe 0.
Eggan stellte in [Egg63] auch eine Möglichkeit vor, Sprachen anhand von einer Eigenschaft
der sie erkennenden, nichtdeterministischen, endlichen Automaten ihrer jeweiligen Sternhöhe
zuzuordnen. Diese Zuordnung lieferte den Beweis, dass es zu jeder Sternhöhe eine reguläre
Sprache gibt, die nicht in den niedrigeren Sternhöhen enthalten ist. Die verallgemeinerte
Sternhöhe ist analog zur Sternhöhe definiert, nur betrachtet sie verallgemeinerte reguläre
Ausdrücke, welche zusätzlich zu Buchstaben, Vereinigung, Konkatenation und Kleene-Stern
auch das Komplement in Σ∗ als Operation erlauben. Bei der verallgemeinerten Sternhöhe ist
bereits das Unterscheiden von Sprachen der Höhen 0 von dem Rest der regulären Sprachen
schwieriger. Sprachen mit verallgemeinerter Sternhöhe 0 werden als sternfrei bezeichnet.
M.P. Schützenberger zeigte in [Sch65], dass eine Sprache genau dann sternfrei ist, wenn
ihr syntaktisches Monoid aperiodisch ist. Die Frage, ob es Sprachen mit verallgemeinerter
Sternhöhe 2 gibt, ist bisher unbeantwortet. Da Monoide, die L erkennen, auch das Komple-
ment von L erkennen, bieten sich diese als möglicher Gegenstand der Untersuchungen zur
verallgemeinerten Sternhöhe an.
Als mögliche Forschungsrichtung für dieses Problem, aber auch um eine Untersuchung des
Einflusses, den der Kleene-Stern auf reguläre Sprachen hat, zu ermöglichen, wurde deshalb im
Rahmen dieser Bachelorarbeit eine algebraische Konstruktion für den Kleene-Stern regulärer
Sprachen entworfen.
Die Konstruktion wurde in zwei Varianten aufgeteilt, die allgemeine und die spezielle Stern-
konstruktion.
Die allgemeine Sternkonstruktion konstruiert auf Basis eines Monoids M ein neues Monoid
⋆(M), welches alle L∗ erkennt, deren L von M erkannt wurde.
Die spezielle Sternkonstruktion ergibt für ein Monoid M und eine erkennende Menge P ⊆ M
mit⋆(M, P) ein Monoid, das jene L∗ erkennt, deren L von M so erkannt werden, dass P das
Bild von L in M ist.
7
1 Einleitung
Die Beweise der Konstruktionen laufen bis auf kleine Unterschiede identisch ab, und basieren
auf der Idee, sich alle möglichen Unterteilungen des Wortes in dem gegebenen Monoid M in
dem Bild des Wortes in⋆(M) zu merken. Wenn man dann zwei Teilworte aneinanderfügen
möchte, kann man alle möglichen Unterteilungen des neuen Wortes aus den Unterteilungen
der beiden Teilworte erschließen, ohne die Worte selbst zu betrachten.
8
2 Allgemeine Sternkonstruktion
In diesem Kapitel soll eine Monoidkonstruktion vorgestellt werden, die aus einem gegebenen
Monoid M ein neues Monoid konstruiert, das für alle Sprachen L, die von M erkannt werden,
L∗ erkennt. Die Intention bei der Konstruktion ist, dass ein Wort w aus Σ∗ auf eine Menge
abgebildet wird, die das Bild von w in dem ursprünglichen Monoid M enthält. Zusätzlich
dazu enthält die Menge die Tupel (m1, N, m2), wenn es eine Zerlegung von w in Teilworte
u1..uj so gibt, dass m1 das Bild von u1 in dem Monoid M ist, m2 das Bild von uj und die Bilder
von den mittleren ui sich in der Menge N befinden.
Definition 1. Für ein gegebenes Monoid (M, ∗) definieren wir die Operation
⋆ : {1} ∪ M ∪ (M×P(M)× M)→ P(M ∪ (M×P(M)× M)) ∪ {1}
durch
m1 ⋆m2 = {m1 ∗m2, (m1,∅, m2)}
m1 ⋆ (m2, N, m3) = {(m1 ∗m2, N, m3), (m1, {m2} ∪ N, m3)}
(m1, N, m2) ⋆m3 = {(m1, N, m2 ∗m3), (m1, {m2} ∪ N, m3)}
(m1, N, m2) ⋆ (m3, P, m4) = {(m1, N ∪ P ∪ {m2 ∗m3}, m4), (m1, N ∪ P ∪ {m2, m3}, m4)}
Die 1 sei neutrales Element.
Zusätzlich dazu soll das Bild einer Menge von Elementen unter ⋆ der Vereinigung der Bilder der
Elemente entsprechen.
Lemma 1. Die Multiplikation ⋆ ist assoziativ.
Beweis. (Mengenklammern teilweise zur besseren Lesbarkeit weggelassen)
1a (m1 ⋆m2) ⋆m3 =
{m1 ∗m2, (m1,∅, m2)} ⋆m3 =
{m1 ∗m2 ∗m3, (m1 ∗m2,∅, m3),
(m1,∅, m2 ∗m3), (m1, {m2}, m3)}
1b m1 ⋆ (m2 ⋆m3) =
m1 ⋆ {m2 ∗m3, (m2,∅, m3)} =
{m1 ∗m2 ∗m3, (m1,∅, m2 ∗m3),
(m1 ∗m2,∅, m3), (m1, {m2}, m3)}
9
2 Allgemeine Sternkonstruktion
2a (m1 ⋆m2) ⋆ (m3, N, m4) =
{m1 ∗m2, (m1,∅, m2)} ⋆ (m3, N, m4) =
{(m1 ∗m2 ∗m3, N, m4), (m1 ∗m2, {m3} ∪ N, m4),
(m1, N ∪ {m2 ∗m3}, m4), (m1, N ∪ {m2, m3}, m4)}
2b m1 ⋆ (m2 ⋆ (m3, N, m4)) =
m1 ⋆ {(m2 ∗m3, N, m4), (m2, N ∪ {m3}, m4)} =
{(m1 ∗m2 ∗m3, N, m4), (m1, N ∪ {m2 ∗m3}, m4),
(m1 ∗m2, N ∪ {m3}, m4), (m1, N ∪ {m2, m3}, m4)}
3a (m1 ⋆ (m2, N, m3)) ⋆m4 =
{(m1 ∗m2, N, m3), (m1, N ∪ {m2}, m3)} ⋆m4 =
{(m1 ∗m2, N, m3 ∗m4), (m1 ∗m2, N ∪ {m3}, m4),
(m1, N ∪ {m2}, m3 ∗m4), (m1, N ∪ {m2, m3}, m4)}
3b m1 ⋆ ((m2, N, m3) ⋆m4) =
m1 ⋆ {(m2, N, m3 ∗m4), (m2, N ∪ {m3}, m4)} =
{(m1 ∗m2, N, m3 ∗m4), (m1, N ∪ {m2}, m3 ∗m4),
(m1 ∗m2, N ∪ {m3}, m4), (m1, N ∪ {m2, m3}, m4)}
4a (m1 ⋆ (m2, N, m3)) ⋆ (m4, P, m5) =
{(m1 ∗m2, N, m3), (m1, N ∪ {m2}, m3)} ⋆ (m4, P, m5) =
{(m1 ∗m2, N ∪ P ∪ {m3 ∗m4}, m5), (m1 ∗m2, N ∪ P ∪ {m3, m4}, m5),
(m1, N ∪ P ∪ {m2, m3 ∗m4}, m5), (m1, N ∪ P ∪ {m2, m3, m4}, m5)}
4b m1 ⋆ ((m2, N, m3) ⋆ (m4, P, m5)) =
m1 ⋆ {(m2, N ∪ P ∪ {m3 ∗m4}, m5), (m2, N ∪ P ∪ {m3, m4}, m5)} =
{(m1 ∗m2, N ∪ P ∪ {m3 ∗m4}, m5), (m1, N ∪ P ∪ {m2, m3 ∗m4}, m5),
(m1 ∗m2, N ∪ P ∪ {m3, m4}, m5), (m1, N ∪ P ∪ {m2, m3, m4}, m5)}
5a ((m1, N, m2) ⋆m3) ⋆ (m4, P, m5) =
{(m1, N, m2 ∗m3), (m1, N ∪ {m2}, m3)} ⋆ (m4, P, m5) =
{(m1, N ∪ P ∪ {m2 ∗m3 ∗m4}, m5), (m1, N ∪ P ∪ {m2 ∗m3, m4}, m5),
(m1, N ∪ P ∪ {m2, m3 ∗m4}, m5), (m1, N ∪ P ∪ {m2, m3, m4}, m5)}
5b (m1, N, m2) ⋆ (m3 ⋆ (m4, P, m5)) =
(m1, N, m2) ⋆ {(m3 ∗m4, P, m5), (m3, P ∪ {m4}, m5)} =
{(m1, N ∪ P ∪ {m2 ∗m3 ∗m4}, m5), (m1, N ∪ P ∪ {m2, m3 ∗m4}, m5),
(m1, N ∪ P ∪ {m2 ∗m3, m4}, m5), (m1, N ∪ P ∪ {m2, m3, m4}, m5)}
6a ((m1, N, m2) ⋆ (m3, P, m4)) ⋆ (m5, Q, m6) =
{(m1, N ∪ P ∪ {m2 ∗m3}, m4), (m1, N ∪ P ∪ {m2, m3}, m4)} ⋆ (m5, Q, m6) =
{(m1, N ∪ P ∪Q ∪ {m2 ∗m3, m4 ∗m5}, m6),
(m1, N ∪ P ∪Q ∪ {m2 ∗m3, m4, m5}, m6),
(m1, N ∪ P ∪Q ∪ {m2, m3, m4 ∗m5}, m6),
(m1, N ∪ P ∪Q ∪ {m2, m3, m4, m5}, m6)}
10
6b (m1, N, m2) ⋆ ((m3, P, m4) ⋆ (m5, Q, m6)) =
(m1, N, m2) ⋆ {(m3, P ∪Q ∪ {m4 ∗m5}, m6), (m3, P ∪Q ∪ {m4, m5}, m6)} =
{(m1, N ∪ P ∪Q ∪ {m2 ∗m3, m4 ∗m5}, m6),
(m1, N ∪ P ∪Q ∪ {m2, m3, m4 ∗m5}, m6),
(m1, N ∪ P ∪Q ∪ {m2 ∗m3, m4, m5}, m6),
(m1, N ∪ P ∪Q ∪ {m2, m3, m4, m5}, m6)}
Die Beweise zu den Spiegelungen von 2 und 4 laufen aufgrund der Symmetrie von ⋆ ebenso
ab.
Definition 2. Für ein gegebenes Monoid M definieren wir⋆(M) als den Abschluss von M
∪{1} unter ⋆, wobei die Elemente von⋆(M) jetzt noch auf die jeweils kleinste Menge C vergrößert
werden, für die folgendes gilt:
∀Q ⊇ N : (m1, N, m2) ∈ C ⇒ (m1, Q, m2) ∈ C
Das Zusammenfassen der Mengen auf die nächstgrößere gültige funktioniert, da bei der Multiplikation
die Menge nur um von der Menge unabhängige Elemente größer wird und die kleineren Mengen
bereits alle relevanten Informationen für die Multiplikation und späteres vergrößern enthalten (nämlich
die unterschiedlichen kleinsten Mengen für jedes Pre-und Suffix).
⋆(M) ist endlich, da⋆(M) Teilmenge von P(M ∪ (M×P(M)× M)) ist.
Das Zusammenfassen dient dazu, die Konstruktion an die am Anfang des Kapitels genannte Intention
anzupassen.
Satz 1. Für jede Sprache L die durch φ von M erkannt wird, erkennt⋆(M) durch ψ mit
• ψ(ε) = 1
• ∀a ∈ Σ : ψ(a) = {φ(a)}
• ∀w ∈ Σ+ : ψ(w) = ψ(a1) ⋆ ... ⋆ ψ(an) für w = a1...an und ai ∈ Σ
die Sprache L∗.
Lemma 2. Für die so konstruierten ψ gilt:
C ∈ ψ(L+)⇒ C enthält m1 oder (m2, N, m3) mit mi ∈ φ(L) und N ⊆ φ(L)
Beweis. Für jedes C ∈ ψ(L+) lässt sich ein w ∈ L+ wählen, für das ψ(w) = C gilt.
Da w ∈ L+ ist, existiert eine Zerlegung w = u1...un mit ui ∈ L.
Für solche Zerlegungen gilt φ(u1) ⋆ ... ⋆ φ(un) ⊆ ψ(w), denn aus der Definition von ⋆ und ψ
folgt φ(ui) ∈ ψ(ui).
11
2 Allgemeine Sternkonstruktion
Aus der Definition von ⋆ ist außerdem leicht ersichtlich, dass auch
(φ(u1), {φ(u2), .., φ(un−1)}, φ(un)) ∈ ψ(w)
bzw.
φ(u1) ∈ ψ(w) für n = 1
gelten muss.
Lemma 3. Enthält ein C ∈ ⋆(M) ein m1 oder ein (m2, N, m3) mit mi ∈ φ(L) und N ⊆
φ(L), so gilt:
ψ−1(C) ⊆ L+
Beweis. Ist ψ−1(C) leer, bleibt nichts zu zeigen.
Sei also w ∈ ψ−1(C).
Enthält C jetzt m ∈ φ(L), so ist w ∈ L.
Enthält C (m1, N, m2) mit mi ∈ φ(L) und N ⊆ φ(L), dann lassen sich die Buchstaben a1..an =
w (ai ∈ Σ) von links an zu ui ∈ Σ∗ so zusammenfassen, dass für die
ui = aj+1...ak k 
 j
folgende Bedingungen gelten:
(m1, N, m2) ∈ φ(u1) ⋆ .. ⋆ φ(ui) ⋆ ψ(ak+1..an)
(m1, N, m2) /∈ φ(u1) ⋆ .. ⋆ φ(ui−1) ⋆ φ(a1...aj+1) ⋆ ψ(aj+2..an)
Eine Zerlegung des Wortes, welche die erste Bedingung erfüllt, existiert immer, da für a ∈
Σ φ(a) = ψ(a) ist. Danach muss nur zusammengefasst werden um Bedingung 2 zu erfüllen.
Ist nun w = u1..uk diese zusammengefasste Zerlegung, dann gilt
(m1, N, m2) ∈ φ(u1) ⋆ .. ⋆ φ(uk)
Außerdem wissen wir aufgrund der Konstruktion, dass (m1, N, m2) nur aus Operationen
entstehen kann, in denen die Multiplikation * nicht verwendet wird, da sonst die beiden
Elemente, deren Bilder multipliziert werden, in der Zerlegung bereits zusammengefasst
worden wären.
Aus den verbleibenden Operationen folgt
φ(u1) = m1 und φ(uk) = m2 und φ(ui) ∈ N für 1 < i < k
Da {m1, m2} ∪ N Teilmenge von φ(L) ist, sind die ui ∈ L und damit w ∈ L+.
Kombinieren wir Lemma 2 und Lemma 3 mit dem Wissen, dass ψ−1(ε) = ε ist, ist der Beweis
von Satz 1 vollständig.
12
3 Spezielle Sternkonstruktion
In diesem Kapitel betrachten wir eine komprimierte Version der Monoidkonstruktion aus
Kapitel 2, die aus einem gegebenen Monoid M ein neues Monoid konstruiert, das für alle
Sprachen L, die von M mit P als Bild von L in M erkannt werden, L∗ erkennt. Die Intention
bei dieser Konstruktion ist, dass ein Wort w aus Σ∗ auf eine Menge abgebildet wird, die das
Bild von w in dem ursprünglichen Monoid M enthält. Zusätzlich dazu enthält die Menge die
Tupel (m1, m2), wenn es eine Zerlegung von w in Teilworte u1..uj so gibt, dass m1 das Bild
von u1 in dem Monoid M ist, m2 das Bild von uj und die Bilder von den mittleren ui sich in
der erkennenden Menge P befinden.
Definition 3. Für ein gegebenes Monoid (M, ∗) und ein P ⊆ M definieren wir die Operation
⋆ : {1} ∪ M ∪ (M× M)→ {1} ∪ P(M ∪ (M× M))
m1 ⋆m2 = {m1 ∗m2, (m1, m2)}
m1 ⋆ (m2, m3) =
{(m1, m3), (m1 ∗m2, m3)} falls m2 ∈ P
{(m1 ∗m2, m3)} falls m2 /∈ P
(m1, m2) ⋆m3 =
{(m1, m2 ∗m3), (m1, m3)} falls m2 ∈ P
{(m1, m2 ∗m3)} falls m2 /∈ P
(m1, m2) ⋆ (m3, m4) =
{(m1, m4)} falls m2, m3 ∈ P oder m2 ∗m3 ∈ P
{} sonst
Die 1 sei neutrales Element.
Zusätzlich dazu soll das Bild einer Menge von Elementen unter ⋆ der Vereinigung der Bilder der
Elemente entsprechen.
Lemma 4. Die Multiplikation ⋆ ist assoziativ.
Beweis. (Mengenklammern teilweise zur besseren Lesbarkeit weggelassen)
1a (m1 ⋆m2) ⋆m3 =
{m1 ∗m2, (m1, m2)} ⋆m3 =
{m1 ∗m2 ∗m3, (m1 ∗m2, m3), (m1, m2 ∗m3), (m1, m3)} falls m2 ∈ P
{m1 ∗m2 ∗m3, (m1 ∗m2, m3), (m1, m2 ∗m3)} falls m2 /∈ P
13
3 Spezielle Sternkonstruktion
1b m1 ⋆ (m2 ⋆m3) =
m1 ⋆ {m2 ∗m3, (m2, m3)} =
{m1 ∗m2 ∗m3, (m1, m2 ∗m3), (m1 ∗m2, m3), (m1, m3)} falls m2 ∈ P
{m1 ∗m2 ∗m3, (m1, m2 ∗m3), (m1 ∗m2, m3), (m1, m3)} falls m2 /∈ P
2a (m1 ⋆m2) ⋆ (m3, m4) =
{m1 ∗m2, (m1, m2)} ⋆ (m3, m4) =
{(m1 ∗m2 ∗m3, m4), (m1 ∗m2, m4), (m1, m4)} falls m3 ∈ P ∧ (m2 ∗m3 ∈ P ∨m2, m3 ∈ P)
{(m1 ∗m2 ∗m3, m4), (m1, m4)} falls m3 /∈ P ∧m2 ∗m3 ∈ P
{(m1 ∗m2 ∗m3, m4), (m1 ∗m2, m4)} falls m3 ∈ P ∧m2 ∗m3 /∈ P ∧m2 /∈ P
{(m1 ∗m2 ∗m3, m4)} falls m3 /∈ P ∧m2 ∗m3 /∈ P
2b m1 ⋆ (m2 ⋆ (m3, m4)) =
m1 ⋆ {(m2 ∗m3, m4), (m2, m4)} falls m3 ∈ P
m1 ⋆ {(m2 ∗m3, m4)} falls m3 /∈ P
=
{(m1 ∗m2 ∗m3, m4), (m1, m4), (m1 ∗m2, m4)} falls m3 ∈ P ∧ (m2 ∗m3 ∈ P ∨m2, m3 ∈ P)
{(m1 ∗m2 ∗m3, m4), (m1, m4)} falls m3 /∈ P ∧m2 ∗m3 ∈ P
{(m1 ∗m2 ∗m3, m4), (m1 ∗m2, m4)} falls m3 ∈ P ∧m2 ∗m3 /∈ P ∧m2 /∈ P
{(m1 ∗m2 ∗m3, m4)} falls m3 /∈ P ∧m2 ∗m3 /∈ P
3a (m1 ⋆ (m2, m3)) ⋆m4 =
{(m1 ∗m2, m3), (m1, m3)} ⋆m4 falls m2 ∈ P
{(m1 ∗m2, m3)} ⋆m4 falls m2 /∈ P
=
{(m1 ∗m2, m3 ∗m4), (m1 ∗m2, m4), (m1, m3 ∗m4), (m1, m4)} falls m2, m3 ∈ P
{(m1 ∗m2, m3 ∗m4), (m1, m3 ∗m4), (m1, m4)} falls m2 ∈ P ∧m3 /∈ P ∧m2 ∗m3 ∈ P
{(m1 ∗m2, m3 ∗m4), (m1 ∗m2, m4), (m1, m4)} falls m2 /∈ P ∧m3 ∈ P ∧m2 ∗m3 ∈ P
{(m1 ∗m2, m3 ∗m4), (m1, m4)} falls m2, m3 /∈ P ∧m2 ∗m3 ∈ P
{(m1 ∗m2, m3 ∗m4)} falls m2, m3 /∈ P ∧m2 ∗m3 /∈ P
3b m1 ⋆ ((m2, m3) ⋆m4) =
m1 ⋆ {(m2, m3 ∗m4), (m2, m4)} falls m3 ∈ P
m1 ⋆ {(m2, m3 ∗m4)} falls m3 /∈ P
=
{(m1 ∗m2, m3 ∗m4), (m1, m3 ∗m4), (m1 ∗m2, m4), (m1, m4)} falls m2, m3 ∈ P
{(m1 ∗m2, m3 ∗m4), (m1, m3 ∗m4), (m1, m4)} falls m2 ∈ P ∧m3 /∈ P ∧m2 ∗m3 ∈ P
{(m1 ∗m2, m3 ∗m4), (m1 ∗m2, m4), (m1, m4)} falls m2 /∈ P ∧m3 ∈ P ∧m2 ∗m3 ∈ P
{(m1 ∗m2, m3 ∗m4), (m1, m4)} falls m2, m3 /∈ P ∧m2 ∗m3 ∈ P
{(m1 ∗m2, m3 ∗m4)} falls m2, m3 /∈ P ∧m2 ∗m3 /∈ P
14
4a (m1 ⋆ (m2, m3)) ⋆ (m4, m5) =
{(m1 ∗m2, m3), (m1, m3)} ⋆ (m4, m5) falls m2 ∈ P
{(m1 ∗m2, m3)} ⋆ (m4, m5) falls m2 /∈ P
=
{(m1 ∗m2, m5), (m1, m5)} falls (m3 ∗m4 ∈ P ∨m3, m4 ∈ P) ∧m2 ∈ P
{(m1 ∗m2, m5)} falls (m3 ∗m4 ∈ P ∨m3, m4 ∈ P) ∧m2 /∈ P
{} falls (m3 ∗m4 /∈ P ∧m3, m4 /∈ P)
4b m1 ⋆ ((m2, m3) ⋆ (m4, m5)) =
m1 ⋆ {(m2, m5)} falls (m3 ∗m4 ∈ P ∨m3, m4 ∈ P)
m1 ⋆ {} falls (m3 ∗m4 /∈ P ∧m3, m4 /∈ P)
=
{(m1 ∗m2, m5), (m1, m5)} falls (m3 ∗m4 ∈ P ∨m3, m4 ∈ P) ∧m2 ∈ P
{(m1 ∗m2, m5)} falls (m3 ∗m4 ∈ P ∨m3, m4 ∈ P) ∧m2 /∈ P
{} falls (m3 ∗m4 /∈ P ∧m3, m4 /∈ P)
5a ((m1, m2) ⋆m3) ⋆ (m4, m5) =
{(m1, m2 ∗m3), (m1, m3)} ⋆ (m4, m5) falls m2 ∈ P
{(m1, m2 ∗m3)} ⋆ (m4, m5) falls m2 /∈ P
=
{(m1, m5)} falls (m2, m3, m4 ∈ P) ∨ (m2 ∗m3, m4 ∈ P) ∨ (m2, m3 ∗m4 ∈ P) ∨ (m2 ∗m3 ∗
m4 ∈ P)
{} sonst
5b (m1, m2) ⋆ (m3 ⋆ (m4, m5)) =
(m1, m2) ⋆ {(m3 ∗m4, m5), (m3, m5)} falls m4 ∈ P
(m1, m2) ⋆ {(m3 ∗m4, m5)} falls m4 /∈ P
=
{(m1, m5)} falls (m2, m3, m4 ∈ P) ∨ (m2 ∗m3, m4 ∈ P) ∨ (m2, m3 ∗m4 ∈ P) ∨ (m2 ∗m3 ∗
m4 ∈ P)
{} sonst
6a ((m1, m2) ⋆ (m3, m4)) ⋆ (m5, m6) =
{(m1, m4)} ⋆ (m5, m6) falls m2, m3 ∈ P ∨m2 ∗m3 ∈ P
{} ⋆ (m5, m6) sonst
=
{(m1, m6)} falls (m2, m3 ∈ P ∨m2 ∗m3 ∈ P) ∧ (m4, m5 ∈ P ∨m4 ∗m5 ∈ P)
{} sonst
6b (m1, m2) ⋆ ((m3, m4) ⋆ (m5, m6)) =
(m1, m2) ⋆ {(m3, m6)} falls m4, m5 ∈ P ∨m4 ∗m5 ∈ P
{} sonst
=
{(m1, m6)} falls (m2, m3 ∈ P ∨m2 ∗m3 ∈ P) ∧ (m4, m5 ∈ P ∨m4 ∗m5 ∈ P)
{} sonst
Die Beweise zu den Spiegelungen von 2 und 4 laufen aufgrund der Symmetrie von ⋆ ebenso
ab.
15
3 Spezielle Sternkonstruktion
Definition 4. Für ein gegebenes Monoid (M, *) und eine erkennende Menge P ⊆ M definieren wir⋆(M, P)
als den Abschluss von M ∪ {1} unter ⋆P .
⋆(M, P) ist endlich, da⋆(M, P) ⊆ P(M ∪ (M× M))
Satz 2. Für jede Sprache L die durch φ von M erkannt wird, erkennt⋆(M, P) durch ψ mit
ψ(ε) = 1
∀a ∈ Σ : ψ(a) = {φ(a)} und
∀w ∈ Σ+ : ψ(w) = ψ(a1) ⋆ ... ⋆ ψ(an) für w = a1...an und ai ∈ Σ
die Sprache L∗.
Lemma 5. Für die so konstruierten ψ gilt:
C ∈ ψ(L+)⇒ C enthält m1 oder (m2, m3) mit mi ∈ P = φ(L)
Beweis. Für jedes C ∈ ψ(L+) lässt sich ein w ∈ L+ wählen, für das ψ(w) = C gilt.
Da w ∈ L+ ist, existiert eine Zerlegung w = u1...un mit ui ∈ L.
Für solche Zerlegungen gilt φ(u1) ⋆ ... ⋆ φ(un) ⊆ ψ(w), denn aus den Definitionen von ⋆ und
ψ folgt φ(ui) ∈ ψ(ui).
Aus der Definition von ⋆ ist außerdem leicht ersichtlich, dass auch
(φ(u1), φ(un)) ∈ ψ(w)
bzw.
φ(u1) ∈ ψ(w) für n = 1
gelten muss.
Lemma 6. Enthält ein C ∈⋆(M, P) ein m1 oder ein (m2, m3) mit mi ∈ P, so gilt:
ψ−1(C) ⊆ L+
Beweis. Ist ψ−1(C) leer, bleibt nichts zu zeigen.
Sei also w ∈ ψ−1(C).
Enthält C jetzt m ∈ φ(L), so ist w ∈ L.
Enthält C (m1, m2) mit mi ∈ φ(L), dann lassen sich die Buchstaben a1..an = w (ai ∈ Σ) zu
ui ∈ Σ∗ so zusammenfassen, dass für die ui folgende Bedingungen gelten:
w = u1..uk
(m1, m2) ∈ φ(u1) ⋆ .. ⋆ φ(uk)
(m1, m2) /∈ φ(u1) ⋆ .. ⋆ φ(ui−1ui) ⋆ ψ(ui+1).. ⋆ ψ(uk)
16
Eine Zerlegung des Wortes, welche die erste Bedingung erfüllt, existiert mit ui = ai immer, da
für a ∈ Σ φ(a) = ψ(a) ist. Danach muss nur zusammengefasst werden um Bedingung 2 zu
erfüllen.
Ist nun w = u1..uk diese zusammengefasste Zerlegung, dann gilt
(m1, m2) ∈ φ(u1) ⋆ .. ⋆ φ(uk)
Außerdem wissen wir aufgrund der Konstruktion der ui, dass für die Entstehung des (m1, m2)
in jedem Schritt das nächste φ(ui) nicht durch * an φ(ui+1) multipliziert wird, da sonst die
beiden Elemente, deren Bilder multipliziert werden, in der Zerlegung bereits zusammenge-
fasst worden wären. Es muss also jedes φ(uj) für 1 < j < k selbst in P sein.
Es gilt also:
φ(u1) = m1 und φ(uk) = m2 und φ(ui) ∈ P für 1 < i < k
Da {m1, m2} Teilmenge von P ist, sind alle ui ∈ L und damit w ∈ L+.
Kombinieren wir Lemma 5 und Lemma 6 mit dem Wissen, dass ψ−1(ε) = ε ist, ist der Beweis
von Satz 2 vollständig.
17

4 Zusammenfassung und Ausblick
Es wurden zwei algebraische Konstruktionen für den Kleene-Stern regulärer Sprachen be-
trachtet.
Die erste der beiden ist dazu geeignet, aus einem Monoid M ein neues Monoid zu erzeugen,
das alle L∗ erkennt, deren L von M erkannt wurde. Da dieses Monoid eine deutlich größere
und komplexere Struktur hat, als es für ein bestimmtes L∗ nötig wäre, gibt es noch eine zweite
Konstruktion.
Diese ist zusätzlich zu M noch von einer erkennenden Teilmenge von M abhängig. Durch das
Einschränken auf das Erkennen der L∗, deren L zu dieser erkennenden Menge gehören, wird
die Konstruktion deutlich kleiner und übersichtlicher.
Ausblick
Im Rahmen dieser Arbeit konnten leider keine weiterführenden Eigenschaften der Kon-
struktionen untersucht werden. Weitere Erkenntnisse zu dem Einfluss des Kleene-Sterns auf
reguläre Sprachen könnten aber möglicherweise durch Untersuchung von Zusammenhängen-
den algebraischen Eigenschaften in M und⋆(M) gewonnen werden. Untersuchungen der
Größe von⋆(M) in Abhängigkeit von Eigenschaften von M könnten außerdem Hinweise auf
eine mögliche Klassifizierung der Sprachen geben, die durch den Kleene-Stern an Komplexität
gewinnen, und ebenso auf eine mögliche Klassifizierung für die Sprachen, die an Komplexität
verlieren. Der Maßstab für die Komplexität sollte vermutlich die Größe des zugehörigen
syntaktischen Monoides sein.
19

Literaturverzeichnis
[Egg63] L. C. Eggan. Transition graphs and the star-height of regular events. Michigan
Mathematical Journal, 10(4):385–397, 1963. (Zitiert auf Seite 7)
[Sch65] M. P. Schützenberger. On Finite Monoids Having Only Trivial Subgroups. Inf.
Comput., 8(2):190–194, 1965. (Zitiert auf Seite 7)
21

Erklärung
Ich versichere, diese Arbeit selbstständig verfasst zu haben.
Ich habe keine anderen als die angegebenen Quellen benutzt
und alle wörtlich oder sinngemäß aus anderen Werken über-
nommene Aussagen als solche gekennzeichnet. Weder diese
Arbeit noch wesentliche Teile daraus waren bisher Gegen-
stand eines anderen Prüfungsverfahrens. Ich habe diese Ar-
beit bisher weder teilweise noch vollständig veröffentlicht.
Das elektronische Exemplar stimmt mit allen eingereichten
Exemplaren überein.
Ort, Datum, Unterschrift