Multiplicación de las lenguas

Question

3. Suponga que tiene dos lenguas L1 y L2 sobre el alfabeto {a, b}. Indique en un ejemplo de L1 y L2 tal que |L1 - L2| < |L1| - |L2|. Para todas las opciones posibles de L1, L2, ¿cuál es el menor valor de |L1| + |L2| tal que |L1 - L2| < |L1| - |L2|? Demuestre por qué es cierto. (Tenga en cuenta que - es la multiplicación normal multiplicación cuando se trata de números como los tamaños de los conjuntos).

Definición de lenguaje: un lenguaje es un conjunto de cadenas. Un idioma se escribe con un alfabeto. L * es un lenguaje

Definición de cardinalidad: |w| = 0 si w =

|ax| = 1 + |x| si w = ax donde a y x *

abc| = 1 + |bc| = 1 + 1 + |c| = 1 + 1 + 1 + || = 1 + 1 + 0 = 3

He intentado probarlo pero sigo teniendo problemas para entenderlo. Todos los lenguajes que se me ocurren tienen la misma cardinalidad multiplicada juntos o por separado

Answer 1

Si miramos todas las combinaciones $vw$ tal que $v\in L_1$ y $w\in L_2$ entonces hay un total de $|L_1|\cdot |L_2|$ de tales combinaciones, por lo que para tener $|L_1\cdot L_2|<|L_1|\cdot |L_2|$ necesitamos al menos dos combinaciones $vw$ y $v'w'$ tal que $vw=v'w'$ pero $v\neq v'$ (y por lo tanto $w\neq w'$ ).

Así que necesitamos tener una cadena combinada que pueda construirse de dos maneras diferentes utilizando una cadena de $L_1$ y una cadena de $L_2$ . Te dejo que encuentres un ejemplo.

---

Para encontrar el menor valor de $|L_1|+|L_2|$ Simplemente probamos caso por caso hasta que encontremos un par de lenguas adecuadas.

• Si uno de los dos idiomas está vacío, entonces $|L_1\cdot L_2|=0$ porque no podemos construir ninguna cadena compuesta a partir de un lenguaje vacío, y $|L_1|\cdot|L_2|=0$ ya que multiplicamos por cero.
• Si cualquiera de las dos lenguas tiene un solo elemento, digamos $|L_1|=1$ entonces vemos de forma similar que $|L_1\cdot L_2|=|L_1|\cdot |L_2|=|L_2|$ .
• El valor más pequeño para $|L_1|+|L_2|$ debe ser, por tanto, mayor o igual que $4$ . Hay un ejemplo fácil de encontrar con ambas lenguas que contienen exactamente dos elementos para los que también $|L_1\cdot L_2|<|L_1|\cdot|L_2|=4$ . (Pista: incluso podemos encontrar un ejemplo con $L_1=L_2$ ).