Kleene Sternoperation auf der leeren Sprache

In meinem Lehrbuch heißt es: wobei eine leere Sprache ist. $\emptyset^*=\{\epsilon\}$ $\emptyset$

Wir wissen jedoch, dass , wobei eine beliebige Sprache ist. $L \cdot \emptyset = \emptyset$ $L$

Ich kann dieses Konzept nicht intuitiv erfassen, da die Kleene-Stern-Operation darauf hinweist, dass . $\emptyset^*=\emptyset^0 \cup \emptyset^1 \cup \emptyset^2 \cup \cdots$

Warum ist nicht gleich ? $\emptyset^*$ $\emptyset$

formal-languages kleene-star Sagnik
quelle

Siehe diese Antwort . Grundsätzlich gilt für jede nicht leere Menge , für die Konsistenz der Formel . Dies gilt auch für den Fall, dass die natürlichere Erweiterung ist. Dies ist die übliche Wahl bei Halbringen. Der Rest ergibt sich aus der Definition des Kleene-Sterns.

W

$W$

W^{0} = \emptyset

$W^0=\emptyset$

W^{x} W^{y} = W^{x + y}

$W^xW^y=W^{x+y}$

W = \emptyset

$W=\emptyset$

Babou

Bei Zahlen bleibt jedoch undefiniert, hauptsächlich aufgrund von Kontinuitätsproblemen, wie ich mich erinnere, obwohl es oft zweckmäßig ist, es gleich zu definieren . Siehe

0^{0}

$0^0$

1

$1$

0^{0}

$0^0$

babou

Einfach, weil per Definition für alle ist.

ε \in L^{0} = {ε}

$\varepsilon \in L^0 = \{\varepsilon\}$ $L$

Raphael

@ Raffael Ja. Sie können es so ausdrücken. Aber es ist willkürlich, wenn . Ich sollte meine Antwort wahrscheinlich anders schreiben. Ich versuche zu schwer zu erklären.

L = \emptyset

$L=\emptyset$

Babou

@babou Am Ende ist jede Definition beliebig. Einige Definitionen sind hilfreich, andere nicht. Imho, der Versuch, Intuition in Definitionen als grundlegend zu finden, ist selten hilfreich und manchmal schädlich.

Raphael

Antworten:

Betrachtet man nun die Potenzen einer Sprache so hat man Soll dies über , dh die nicht negativen ganzen Zahlen, konsistent sein , muss man definieren . Wenn Sie davon ausgehen, dass , haben Sie einschließlich unter anderem für . So hätten wir für jeden . Dies wäre also eindeutig inkonsistent. Eine ähnliche Inkonsistenz ergibt sich für jede andere Wahl als , die die Identität für die Sprachverkettung ist. $W$ $W^xW^y=W^{x+y}$ $\mathbb N_0$ $W^0=\{\epsilon\}$ $\emptyset$ $W^x=W^{x+0}=W^xW^0=W^x\emptyset=\emptyset$ $x=1$ $W^1=W=\emptyset$ $W$ $\{\epsilon\}$

Daher ist die einzige konsistente konsistente Definition von für eine nicht leere Menge ist . $W^0$ $W$ $W^0=\{\epsilon\}$

Es ist dann zweckmäßig, die Definition auf den Fall zu erweitern, in dem als . $W=\emptyset$ $\emptyset^0=\{\epsilon\}$

Dies ist nur eine konsistente und bequeme Definition, die häufig in Form von Halbringen verwendet wird. Sie kann jedoch nicht bewiesen werden, im Gegensatz zu dem Fall, in dem keine andere konsistente Definition enthält. $W\neq\emptyset$

Andere Definitionen müssen dann jedoch konsistent angegeben werden, was dies impliziert

\begin{aligned} \emptyset^{*} & = \emptyset^{0} \cup \emptyset^{1} \cup \emptyset^{2} \cup \dots \\ = {ϵ} \cup \emptyset \cup \emptyset \cup \dots \\ = {ϵ} \end{aligned}

$\begin{align} \emptyset^*&=\emptyset^0\cup\emptyset^1\cup\emptyset^2\cup\ldots \\ &=\{\epsilon\}\cup\emptyset\cup\emptyset\cup\ldots\\ &=\{\epsilon\} \end{align}$

Das Thema wird auf vielen Webseiten diskutiert. Im Fall des Zahlenhalbrings (die Ungenauigkeit ist beabsichtigt) wird dies auf dieser Seite ausführlich erläutert: Null gegen Null - Ist ? $0^0=1$ .

Der Halbkreis der Sprachen wird in dieser Antwort beschrieben .

babou
quelle

Diese Antwort hat alle meine Zweifel ausgeräumt. Und die Verbindungen waren ausgezeichnet.

Sagnik

Die Verkettung von Null Worte von ist das leere Wort , so . Allgemeiner gesagt , für eine Sprache , die Kleene Stern besteht aus allen Verkettung von einer beliebigen Anzahl von Wörtern aus , eine beliebige Zahl einschließlich Null Worte . $\emptyset$ $\epsilon$ $\epsilon \in \emptyset^*$ $L$ $L^*$ $L$

Yuval Filmus
quelle

Ich suchte nach einer mathematischeren Erklärung, weil ich nicht in der Lage war, das Konzept der "Verkettung von Nullwörtern" intuitiv zu verstehen. Nachdem ich jedoch die Antwort von @ babou und diese Antwort gelesen hatte, wurden alle meine Zweifel ausgeräumt. Vielen Dank.

Sagnik

"... für eine Sprache L besteht der Kleene-Stern L * aus der gesamten Verkettung einer beliebigen Anzahl von Wörtern aus L, einer beliebigen Anzahl von Wörtern einschließlich Null." Epsilon ist ein Wort. Wie können wir also sagen, dass die Anzahl von null Wörtern Epsilon enthält? Korrigieren Sie mich bitte.

Palak Jain

Die Verkettung von Nullwörtern ist das neutrale Element für die Verkettung, dh das leere Wort. In gleicher Weise ist die Summe der Nullelemente Null, das Produkt der Nullelemente ist Eins, die Vereinigung der Nullmengen ist die leere Menge und so weiter.

Yuval Filmus