¿Es Σ* lo mismo que decir L*

Question

Me estoy confundiendo con los dos. ¿Son lo mismo? El complemento de una lengua L es * - L. ¿Es incorrecto decir L* - L?

Answer 1

Por definición, $L^* = \bigcup_{n \geq 0} L^n$ . También, $\Sigma$ es el lenguaje de todas las palabras de longitud $1$ (de forma equivalente, $\Sigma$ es el alfabeto). Así que $\Sigma^* = \bigcup_{n \geq 0} \Sigma^n$ . No hay ninguna razón especial para suponer que $\Sigma^* = L^*$ . Por ejemplo, supongamos que $\Sigma = \{a,b\}$ mientras que $L = \{a\}$ . Entonces $\Sigma^*$ consiste en todas las palabras de más de $a,b$ , mientras que $L^*$ consiste en todas las palabras de más de $a$ .

De hecho, no es difícil demostrar que $L^* = \Sigma^*$ si $\Sigma \subseteq L$ (ejercicio).