Operación estrella de Kleene en el lenguaje vacío

En mi libro de texto se menciona que: $\emptyset^*=\{\epsilon\}$ donde $\emptyset$ es un idioma vacío.

Sin embargo, sabemos que $L \cdot \emptyset = \emptyset$ , donde $L$ es cualquier lenguaje.

No puedo comprender intuitivamente este concepto porque la operación en estrella de Kleene apunta al hecho de que $\emptyset^*=\emptyset^0 \cup \emptyset^1 \cup \emptyset^2 \cup \cdots$ .

Entonces, ¿por qué $\emptyset^*$ no es igual a $\emptyset$ ?

formal-languages kleene-star Sagnik
fuente

Mira esta respuesta . Básicamente, para cualquier conjunto no vacío

para la consistencia de la fórmula

. Esto se extiende al caso cuando

como la extensión más natural. Esta es la opción habitual en semi-anillos. El resto se deriva de la definición de la estrella de 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

Sin embargo, para los números,

se deja sin definir, principalmente debido a problemas continuos, según recuerdo, aunque a menudo puede ser conveniente definirlo igual a

. Ver

0^{0}

$0^0$

1

$1$

0^{0}

$0^0$

babou

Simplemente porque

para todo , por definición.

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

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

Raphael

@Raphael Sí. Puedes decirlo de esa manera. Pero es arbitrario, afaik, cuando

. Probablemente debería escribir mi respuesta de manera diferente. Trato demasiado de explicar.

L = \emptyset

$L=\emptyset$

babou

@babou Al final, cada definición es arbitraria. Algunas definiciones son útiles, otras no. En mi humilde opinión, tratar de encontrar la intuición en definiciones tan básicas como esta rara vez es útil y, a veces, perjudicial.

Raphael

Respuestas:

Si considera ahora las potencias de un lenguaje , tiene Si desea que esto sea coherente sobre , es decir, los enteros no negativos, debe definir . Si lo como tendrías incluyendo, entre otros, para $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$ . Así tendríamos para cualquier . Por lo tanto, esto sería claramente inconsistente. Una inconsistencia similar surge para cualquier otra opción que no sea , que es la identidad para la concatenación de idiomas. $x=1$ $W^1=W=\emptyset$ $W$ $\{\epsilon\}$

Por lo tanto, la única definición consistente consistente de para un conjunto no vacío es . $W^0$ $W$ $W^0=\{\epsilon\}$

Entonces es conveniente extender la definición al caso cuando como . $W=\emptyset$ $\emptyset^0=\{\epsilon\}$

Esta es solo una definición consistente y conveniente, a menudo adoptada en semi-anillos, pero no se puede probar, a diferencia de este caso cuando donde no hay otra definición consistente. $W\neq\emptyset$

Sin embargo, se deben dar otras definiciones de manera consistente, lo que implica 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}$

El tema se discute en muchas páginas web. En el caso del semi-anillo de números (la falta de precisión es intencional) esto se discute extensamente en esta página: potencia de cero a cero - ¿Es ? $0^0=1$ .

El semi-anillo de idiomas se describe en esta respuesta .

babou
fuente

Esta respuesta despejó todas mis dudas. Y los enlaces fueron excelentes.

Sagnik

La concatenación de cero palabras de es la palabra vacía , entonces . Más generalmente, para un lenguaje , la estrella de Kleene consiste en toda concatenación de cualquier número de palabras de , cualquier número incluyendo cero palabras . $\emptyset$ $\epsilon$ $\epsilon \in \emptyset^*$ $L$ $L^*$ $L$

Yuval Filmus
fuente

Estaba buscando una explicación más matemática porque no podía obtener una comprensión intuitiva del concepto de "concatenación de palabras cero". Sin embargo, después de leer la respuesta de @ babou y esta respuesta, todas mis dudas se aclararon. Gracias.

Sagnik

"... para un idioma L, la estrella de Kleene L * consiste en toda concatenación de cualquier número de palabras de L, cualquier número incluyendo cero palabras" Aquí, ¿cómo implica un número cero de palabras eplison? epsilon es una palabra, entonces, ¿cómo podemos decir que el número cero de palabras incluye epsilon? Corrígeme, por favor.

Palak Jain

La concatenación de palabras cero es el elemento neutral para la concatenación, que es la palabra vacía. Del mismo modo, la suma de cero elementos es cero, el producto de cero elementos es uno, la unión de cero conjuntos es el conjunto vacío, y así sucesivamente.

Yuval Filmus