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