Opération Kleene Star sur la langue vide

Dans mon manuel, il est mentionné que: où est une langue vide. $\emptyset^*=\{\epsilon\}$ $\emptyset$

Cependant, nous savons que , où est n'importe quelle langue. $L \cdot \emptyset = \emptyset$ $L$

Je ne suis pas en mesure de saisir intuitivement ce concept car l'opération de l'étoile de Kleene indique que . $\emptyset^*=\emptyset^0 \cup \emptyset^1 \cup \emptyset^2 \cup \cdots$

Alors pourquoi n'est-il pas égal à ? $\emptyset^*$ $\emptyset$

formal-languages kleene-star Sagnik
la source

Voir cette réponse . Fondamentalement, pour tout ensemble non vide , pour la cohérence de la formule . Ceci est étendu au cas où est l'extension la plus naturelle. C'est le choix habituel en demi-anneaux. Le reste découle de la définition de l'étoile Kleene.

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

Cependant, pour les nombres, n'est pas défini, principalement en raison de problèmes continuty si je me souviens, bien qu'il soit souvent pratique de le définir égal à . Voir

0^{0}

$0^0$

1

$1$

0^{0}

$0^0$

babou

Tout simplement parce que

pour tout , par définition.

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

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

Raphael

@Raphael Oui. Vous pouvez le dire ainsi. Mais c'est arbitraire, afaik, quand

. Je devrais probablement écrire ma réponse différemment. J'essaie trop fort d'expliquer.

L = \emptyset

$L=\emptyset$

babou

@babou Au final, chaque définition est arbitraire. Certaines définitions sont utiles, d'autres non. À mon humble avis, essayer de trouver une intuition dans les définitions aussi basique que cela est rarement utile et parfois nuisible.

Raphael

Réponses:

Si vous considérez maintenant les puissances d'un langage vous avez Si vous voulez que cela soit cohérent sur , c'est-à-dire les entiers non négatifs, vous devez définir . Si vous le considérez comme vous auriez y compris, entre autres, pour $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$ . Donc on aurait pour tout . Cela serait donc manifestement incohérent. Une incohérence similaire se produit pour tout autre choix que , qui est l'identité de la concaténation de la langue. $x=1$ $W^1=W=\emptyset$ $W$ $\{\epsilon\}$

Par conséquent, la seule définition cohérente cohérente de pour un ensemble non vide est . $W^0$ $W$ $W^0=\{\epsilon\}$

Il est alors commode d'étendre la définition au cas où comme . $W=\emptyset$ $\emptyset^0=\{\epsilon\}$

Il s'agit simplement d'une définition cohérente et pratique, souvent adoptée en demi-anneaux, mais elle ne peut pas être prouvée, contrairement au cas où où il n'y a pas d'autre définition cohérente. $W\neq\emptyset$

Cependant, d'autres définitions doivent alors être données de manière cohérente, ce qui implique que

\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}$

Le sujet est abordé sur de nombreuses pages Web. Dans le cas du demi-anneau de nombres (le manque de précision est intentionnel), cela est longuement discuté sur cette page: Zéro à la puissance zéro - Est-ce que ? $0^0=1$ .

Le demi-anneau des langues est décrit dans cette réponse .

babou
la source

Cette réponse a dissipé tous mes doutes. Et les liens étaient excellents.

Sagnik

La concaténation de zéro mot de est le mot vide , donc . Plus généralement, pour un langage , l'étoile de Kleene est constituée de toute concaténation de tout nombre de mots de , tout nombre comprenant zéro mot . $\emptyset$ $\epsilon$ $\epsilon \in \emptyset^*$ $L$ $L^*$ $L$

Yuval Filmus
la source

Je cherchais une explication plus mathématique car je n'arrivais pas à comprendre intuitivement le concept de "concaténation de zéro mot". Cependant, après avoir lu la réponse de @ babou et cette réponse, tous mes doutes se sont dissipés. Je vous remercie.

Sagnik

"... pour une langue L, l'étoile Kleene L * consiste en toute concaténation de n'importe quel nombre de mots de L, n'importe quel nombre comprenant zéro mot" Ici, comment un nombre de mots nul implique-t-il une élection? epsilon est un mot, alors comment dire que zéro nombre de mots inclut epsilon? Corrigez-moi, s'il vous plaît.

Palak Jain

La concaténation de zéro mot est l'élément neutre de la concaténation, qui est le mot vide. De la même manière, la somme des éléments zéro est nulle, le produit des éléments zéro est un, l'union des ensembles zéro est l'ensemble vide, et ainsi de suite.

Yuval Filmus