Kleene-Stern - Kleene star

In der mathematischen Logik und Informatik ist der Kleene-Stern (oder Kleene-Operator oder Kleene-Abschluss ) eine unäre Operation , entweder auf Sätze von Strings oder auf Sätzen von Symbolen oder Zeichen. In der Mathematik ist es häufiger als die freie Monoidkonstruktion bekannt . Die Anwendung des Kleene-Sterns auf eine Menge wird als geschrieben . Es wird häufig für reguläre Ausdrücke verwendet , in dem es von Stephen Kleene eingeführt wurde , um bestimmte Automaten zu charakterisieren , wo es "null oder mehr Wiederholungen" bedeutet.

  1. Wenn ein Satz von Zeichenketten ist, dann definiert als die kleinste Superset der , daß die enthält leere Zeichenfolge und geschlossen unter der Zeichenfolge Verkettungsoperation .
  2. Wenn eine Menge von Symbolen oder Zeichen ist, dann ist die Menge aller Zeichenfolgen über den Symbolen in , einschließlich der leeren Zeichenfolge .

Die Menge kann auch als die Menge beschrieben werden, die die leere Zeichenfolge und alle Zeichenfolgen endlicher Länge enthält, die durch Verketten beliebiger Elemente von erzeugt werden können , was die mehrfache Verwendung desselben Elements ermöglicht. If ist entweder die leere Menge ∅ oder die Singleton-Menge , dann ; wenn eine andere endliche Menge oder abzählbar unendliche Menge ist , dann ist eine abzählbar unendliche Menge. Folglich ist jede formale Sprache über einem endlichen oder abzählbar unendlichen Alphabet abzählbar, da sie eine Teilmenge der abzählbar unendlichen Menge ist .

Die Operatoren werden in Rewrite-Regeln für generative Grammatiken verwendet .

Definition und Notation

Gegeben eine Menge define

(die Sprache, die nur aus dem leeren String besteht),

und definiere rekursiv die Menge

für jeden .

Wenn eine formale Sprache ist, dann ist die -te Potenz der Menge eine Abkürzung für die Verkettung von Mengen mit sich selbst mal. Das heißt, kann als die Menge aller Strings verstanden werden, die als Verkettung von Strings in dargestellt werden können .

Die Definition von Kleene star on ist

Dies bedeutet, dass der Kleene-Sternoperator ein idempotenter unärer Operator ist : für jeden Satz von Strings oder Zeichen, wie für jeden .

Kleene plus

In einigen formalen Sprachstudien (zB AFL-Theorie ) wird eine Variante der Kleene-Sternoperation namens Kleene plus verwendet. Die Kleene plus lässt den Begriff in der obigen Vereinigung weg . Mit anderen Worten, das Kleene-Plus auf ist

oder

Beispiele

Beispiel für einen Kleene-Stern, der auf einen Satz von Saiten angewendet wird:

{"ab","c"} * = { ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}.

Beispiel für Kleene plus angewendet auf Zeichensatz:

{"a", "b", "c"} + = { "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc ", "ca", "cb", "cc", "aaa", "aab", ...}.

Kleene-Stern auf denselben Zeichensatz angewendet:

{"a", "b", "c"} * = { ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}.

Beispiel für Kleene-Stern angewendet auf die leere Menge:

* = {ε}.

Beispiel für Kleene plus angewendet auf die leere Menge:

+ = ∅ ∅ * = { } = ∅,

wobei die Verkettung ein assoziatives und nichtkommutatives Produkt ist.

Beispiel für Kleene plus und Kleene star, angewendet auf das Singleton-Set, das die leere Zeichenfolge enthält:

Wenn , dann auch für jeden , also .

Verallgemeinerung

Strings bilden ein Monoid mit Verkettung als binäre Operation und ε als Identitätselement. Der Kleene-Stern ist für jedes Monoid definiert, nicht nur für Strings. Genauer gesagt sei ( M , ⋅) ein Monoid und SM . Dann ist S * das kleinste Submonoide von M, das S enthält ; das heißt, S * enthält das neutrale Element von M , wobei der Satz S , und ist so , dass , wenn x , yS * , dann xyS * .

Darüber hinaus wird der Kleene-Stern verallgemeinert, indem die *-Operation (und die Vereinigung) in die algebraische Struktur selbst durch den Begriff des vollständigen Sternhalbrings aufgenommen wird .

Siehe auch

Verweise

Weiterlesen