Operacja gwiazdy Kleene na pustym języku

W moim podręczniku wspomniano, że: gdzie to pusty język. $\emptyset^*=\{\epsilon\}$ $\emptyset$

Wiemy jednak, że , gdzie to dowolny język. $L \cdot \emptyset = \emptyset$ $L$

Nie jestem w stanie intuicyjnie zrozumieć tej koncepcji, ponieważ operacja gwiazdy Kleene wskazuje na fakt, że . $\emptyset^*=\emptyset^0 \cup \emptyset^1 \cup \emptyset^2 \cup \cdots$

Dlaczego więc nie jest równe ? $\emptyset^*$ $\emptyset$

formal-languages kleene-star Sagnik
źródło

Zobacz tę odpowiedź . Zasadniczo dla każdego niepustego zestawu , zestaw pusty dla spójności wzoru . Jest to rozszerzone na przypadek, gdy jako bardziej naturalne rozszerzenie. Jest to zwykły wybór w pół-pierścieniach. Reszta wynika z definicji gwiazdy 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

Jednak w przypadku liczb pozostaje niezdefiniowane, głównie z powodu problemów z ciągłością, o ile pamiętam, choć często wygodne może być zdefiniowanie go jako . Patrz

0^{0}

$0^0$

1

$1$

0^{0}

$0^0$

babou

Po prostu dlatego, że dla wszystkich , z definicji.

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

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

Raphael

@Raphael Tak. Możesz to tak ująć. Ale jest to arbitralne, afaik, gdy

L = \emptyset

$L=\emptyset$ . Prawdopodobnie powinienem napisać swoją odpowiedź inaczej. Próbuję zbyt mocno wyjaśnić.

babou

@babou Ostatecznie każda definicja jest dowolna. Niektóre definicje są pomocne, inne nie. Imho próbuje znaleźć intuicję w definicjach tak podstawowych, jak to rzadko jest pomocne, a czasem szkodliwe.

Raphael

Odpowiedzi:

Jeśli weźmiesz teraz pod uwagę moc języka , masz Jeśli chcesz, aby było to spójne z , tj. Liczbami całkowitymi nieujemnymi, musisz zdefiniować . Gdyby przyjąć, że jest to , miałbyś tym między innymi dla $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$ . W ten sposób, że mamy dla każdego . Zatem byłoby to wyraźnie niespójne. Podobna niespójność pojawia się przy każdym wyborze innym niż , który jest tożsamością dla konkatenacji języka. $x=1$ $W^1=W=\emptyset$ $W$ $\{\epsilon\}$

Stąd jedyną spójną spójną definicją dla niepustego zestawu jest . $W^0$ $W$ $W^0=\{\epsilon\}$

Następnie wygodnie jest rozszerzyć definicję na przypadek, gdy jako . $W=\emptyset$ $\emptyset^0=\{\epsilon\}$

Jest to tylko spójna i wygodna definicja, często stosowana w pół-pierścieniach, ale nie można jej udowodnić, w przeciwieństwie do przypadku, gdy gdzie nie ma innej spójnej definicji. $W\neq\emptyset$

Jednak inne definicje muszą być podane w spójny sposób, co implikuje

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

Temat ten jest omawiany na wielu stronach internetowych. W przypadku pół-pierścienia liczb (brak precyzji jest zamierzony) jest to omówione szczegółowo na tej stronie: od zera do potęgi zerowej - czy ? $0^0=1$ .

Pół-język języków jest opisany w tej odpowiedzi .

Babou
źródło

Ta odpowiedź rozwiała wszystkie moje wątpliwości. A linki były doskonałe.

Sagnik

Łączenie zerowych słów z jest pustym słowem , więc . Mówiąc bardziej ogólnie, dla języka gwiazda Kleene składa się z całej konkatenacji dowolnej liczby słów z , dowolnej liczby, w tym słów zerowych . $\emptyset$ $\epsilon$ $\epsilon \in \emptyset^*$ $L$ $L^*$ $L$

Yuval Filmus
źródło

Szukałem bardziej matematycznego wyjaśnienia, ponieważ nie byłem w stanie zrozumieć intuicyjnie pojęcia „konkatenacji zerowych słów”. Jednak po przeczytaniu odpowiedzi @ babou i tej odpowiedzi wszystkie moje wątpliwości zostały wyjaśnione. Dziękuję Ci.

Sagnik

„... dla języka L gwiazda Kleene L * składa się z całej konkatenacji dowolnej liczby słów z L, dowolnej liczby, w tym słów zerowych”. W jaki sposób zerowa liczba słów oznacza eplison? epsilon to słowo, więc jak możemy powiedzieć, że zero słów zawiera epsilon? Proszę mnie poprawić.

Palak Jain

Łączenie zerowych słów jest neutralnym elementem konkatenacji, który jest pustym słowem. W ten sam sposób suma elementów zerowych wynosi zero, iloczyn elementów zerowych wynosi jeden, suma zbiorów zerowych jest zbiorem pustym i tak dalej.

Yuval Filmus