Eine unendliche Sprache kann nicht regelmäßig sein? Was ist eine endliche Sprache?

Question

Ich lese in einem Buch auf Berechenbarkeit:

(Kleenes Satz) ist eine Sprache, regelmäßig, wenn und nur wenn es aus endlichen Sprachen erhalten werden kann, indem die drei Operationen Vereinigung Anwendung Verkettung, Wiederholung eines endliche Anzahl.

Ich kämpfe mit "endlichen Sprachen".

Betrachten Sie diese Sprache: L = a*

Es ist nicht endlich ist. Es ist die Menge {0, a, aa, aaa, ...}, die eindeutig eine unendliche Menge ist (0 = der leere String).

Also ist es eine unendliche Sprache, oder? Das heißt, "unendliche Menge" bedeutet "unendliche Sprache", richtig?

Offensichtlich ist a* eine reguläre Sprache. Und es ist eine unendliche Sprache. Daher kann es nach Kleenes Theorem keine reguläre Sprache sein. Widerspruch.

Ich bin verwirrt. Ich denke, dass ich nicht weiß, was "endliche Sprache" bedeutet.

Answer 1

Sie sind auf dem richtigen Weg, es könnte klarer sein. Kleens Satz drückt die Äquivalenz von drei Aussagen aus

Eine Sprache ist regulär == Eine Sprache kann durch einen regulären Ausdruck ausgedrückt werden == Eine Sprache kann durch einen endlichen Automaten ausgedrückt werden.

Ihr Beispiel ist in der Tat eine normale Sprache. Eine endliche Sprache ist das, was Sie erwarten würden, eine Sprache, die in einer endlichen Menge von Zeit aufgelistet werden kann.

Wenn sie über Wiederholung sprechen, reden sie über den Betrieb Kleen Star, das ist genau das, was a* darstellt, der Satz {empty, a, aa, aaa, aaaa, ...}

EDIT:

ich this link: Kleenes Theorem gefunden haben, die ziemlich viel hilft. Mit "Wiederholung" meinen sie Kleen Star, dann ergibt die ursprüngliche Aussage Sinn. a* ist Kleen_Star(a)

Answer 2

Sehr kurz, Ihre Aussage sagt:

Eine Sprache ist regulär, wenn und nur wenn es ein regulärer Ausdruck für sie ist.

---

Der Teil „kann durch die Anwendung der drei Operationen Union, Verkettung, Wiederholung eine endliche Anzahl von Malen von finite Sprachen erhalten wird“ ist im Wesentlichen eine schnelle verbale Definition eines regulären Ausdrucks.Üblicherweise wird ein regulärer Ausdruck (RE) wird formell ausgehend definiert sind, mit den folgenden Basis Fällen:

• ∅ (das leere Set) ist ein RE
• ε (die leere Zeichenkette) ein RE
• a ist ein RE, wo ein im Alphabet ist

Diese sind alle endliche Sprachen. Wir haben dann erhalten andere REs von die folgenden drei rekursive Regeln eine endliche Anzahl von Malen Anwendung:

• A | B ist ein RE wo beide A und B sind REs
• AB ein RE ist, wo beide A und B sind REs
• A * ist ein RE wo A ist ein RE

---

Am Ende können Sie unendliche Sprachen mit endlichen Beschreibungen (ein regulärer Ausdruck) erstellen.

Answer 3

Eine endliche Sprache ist eine Sprache mit einer endlichen Anzahl von Wörtern. Die einfachsten Fälle sind diejenigen, die überhaupt keine Wörter enthalten, die leere Zeichenfolge und eine einzelne Zeichenfolge, die aus einem einzelnen Symbol besteht (z. B. a in Ihrem Beispiel).

Ich denke, deine Verwirrung kommt davon, die Regel, die du zitierst, falsch zu lesen (wie einige von denen, die die Frage kommentieren). Der Satz von Kleene ist eine Regel, wenn und nur dann, wenn sie aus endlichen Sprachen erhalten werden kann, indem die drei Operationen Vereinigung, Verkettung, Wiederholung eine endliche Anzahl von Malen angewendet werden. Die Passage spricht nicht über die Anzahl von Operationen an Strings, die benötigt werden, um alle Strings in einer Sprache zu erzeugen, sondern über die Anzahl von Operationen in einfacheren Sprachen, die benötigt werden, um die Sprache zu definieren, die definiert wird. Die Sprache, die Sie erwähnen, wird aufgebaut, indem Sie mit einer endlichen Sprache (der Menge {"a"}) beginnen und den Wiederholungsoperator einmal anwenden. Ein anderer und weniger direkter Weg, den Punkt zu setzen, würde nicht Sprachen und Operationen an Sprachen ansprechen, sondern Ausdrücke, die Sprachen und komplexere Ausdrücke verbinden, die sie kombinieren: Eine Sprache ist genau dann regulär, wenn sie mit a bezeichnet werden kann Regulärer Ausdruck, der eine endliche Anzahl von Operatoren enthält.

Nehmen Sie einen Ausdruck wie a, bezeichnet die endliche Sprache, die nur das einzelne Wort "a" enthält. Wir können diesem Ausdruck einen einzelnen Wiederholungsoperator hinzufügen, und wir erhalten a*, die unendliche Sprache, die jede Verkettung von null oder mehr Wörtern aus der ersten Sprache enthält.Jeder endliche Ausdruck E wir ausgehend von Ausdrücke bezeichnen endliche Sprachen und durch die Kombination von einer oder zwei kleineren Ausdrücke F und G mit den Mustern E = F bauen | G, E = FG oder E = F * eine reguläre Sprache bezeichnen wird. Ausdrücke, die endliche Sprachen (Sprachen mit einer endlichen Anzahl von Wörtern) bezeichnen, sind der Grundfall, wenn die Regel in Ausdrücken ausgedrückt wird; Endliche Sprachen sind der Basisfall, wenn die Regel direkt in Sprachen ausgedrückt wird, ohne Umwege zum Ausdruckland.

Wenn wir zulassen, dass union, concatenation und repetion unendlich oft angewendet werden (oder äquivalent, wenn wir unendliche Ausdrücke unter Verwendung der Regeln für reguläre Exressionen zulassen), wird die resultierende Sprache nicht regelmäßig garantiert. Dies ist das Analogon auf der regulären Sprachebene der Beobachtung, dass unendlich große kontextfreie Grammatiken nicht-kontextfreie Sprachen definieren können, wie van Wijngaarden-Grammatiken illustrieren.

Answer 4

Eine unendliche Sprache bedeutet eine Menge mit unendlichen Äquivalenzklassen. Die a * -Sprache hat jedoch nur eine Äquivalenzklasse, was sie zu einer endlichen Sprache macht.