Entendiendo la concatenación del conjunto vacío con cualquier conjunto.

Question

Sé que al concatenar el conjunto vacío con cualquier conjunto se obtiene el conjunto vacío. Así que.., $A \circ \varnothing = \varnothing$ . Aquí $A$ es un conjunto de cadenas y la concatenación ( $\circ$ ) de dos conjuntos de cadenas, $X$ y $Y$ es el conjunto formado por todas las cadenas de la forma $xy$ donde $x\in X$ y $y \in Y$ . (Puede consultar la página 65, ejemplo 1.53 de Introducción a la teoría de la computación por Michael Sipser ). Sin embargo, me siento algo desconcertado cuando trato de entenderlo intuitivamente.

A equivocada La línea de pensamiento hará que uno se pregunte: "Si concatenamos $A$ con $\varnothing$ ¿no debería seguir siendo $A$ ?"

Bueno, una forma de forzarme a entender la respuesta correcta, puede ser, decir que, como estoy concatenando con un conjunto vacío, en realidad no podré realizar la concatenación. La concatenación no existirá en absoluto.

Pido ayuda a los usuarios experimentados para que proporcionen pistas y ejemplos de la vida real que le ayuden a uno a modificar el proceso de pensamiento y le ayuden a entender mejor la respuesta correcta. Hago más hincapié en los ejemplos de la vida real.

Necesito entender esto. No me basta con memorizar la respuesta correcta.

Answer 1

De los comentarios se desprende que el contexto son los conjuntos regulares. Si $A$ y $B$ son conjuntos, definimos $A\circ B=\{ab:a\in A\text{ and }b\in B\}$ . Si $B=\varnothing$ no hay objetos $b\in B$ , por lo que no hay objetos $ab$ tal que $a\in A$ y $b\in B$ Así que.., $A\circ\varnothing=\varnothing$ .

Answer 2

La línea de pensamiento equivocada es casi correcta, de la siguiente manera. Dejemos que $\epsilon$ sea la cadena vacía. Para cualquier cadena $a$ tenemos $a\epsilon=a$ . Dejemos que $\{\epsilon\}$ sea el conjunto que contiene exactamente un elemento, es decir, la cadena vacía. Entonces, para cualquier conjunto de cadenas $A$ tenemos $A\circ\{\epsilon\}=A$ .

La verdadera cuestión, entonces, es confundir $\{\epsilon\}$ con $\varnothing$ . El primero es un conjunto que contiene una cadena; el segundo es un conjunto que contiene cero cadenas.

(Una posible trampa es que algunos formalismos podrían identificar $\epsilon=\varnothing$ . Entonces tenemos que distinguir entre $\{\varnothing\}$ y $\varnothing$ . Esto es teóricamente sencillo, pero significa que hay que tener cuidado con la notación).

Answer 3

Obsérvese que existe una suryección natural desde $A\times B$ en $A\circ B$ . Si $B$ es vacía, el producto es vacío y por lo tanto la concatenación es vacía.

Answer 4

Este buena respuesta me hizo entender perfectamente la cuestión desde un punto de vista matemático. También estaba buscando algunos ejemplos de la vida real, como se indica en mi post original, puede ser de un dominio completamente diferente, para hacer mi comprensión intuitiva mejor.

Anoche me vino a la mente un ejemplo que me gustaría compartir con todos.

Utilicemos la concatenación para indicar el matrimonio entre dos grupos de hombres y mujeres.

Ahora, si nuestro primer conjunto es un grupo de hombres, $M = \{M_1, M_2, M_3\}$ y el segundo conjunto es un grupo de mujeres, $W = \{W_1, W_2\}$ el grupo de posiblemente casados será el conjunto concatenado, $ \begin{align*} C &= M\circ W\\ &= \{M_1,M_2,M_3\}\circ\{W_1,W_2\}\\ &=\{M_1W_1, M_1W_2, M_2W_1, M_2W_2, M_3W_1, M_3W_2\} \end{align*}$

(Ignoremos aquí las cuestiones como quién puede casarse con quién y los matrimonios múltiples, o no debe ser una pareja escrita como pareja ordenada, sólo para mantenerlo simple).

Ahora bien, si el grupo de mujeres está vacío, $W = \varnothing$ Si no hay ninguna mujer disponible para casarse, los matrimonios no se producirán, y el conjunto, el grupo de parejas casadas, estará vacío, $C = M\circ W =\varnothing$ .