En cuanto a la expresión regular, ¿por qué no existen las siguientes cadenas en la expresión?

Question

Sea L el lenguaje definido por la expresión regular:

(a U b U c)((ab U ac U b)*(a U b) U (aa)*)

el libro de respuestas dice que 'aaaa' y 'aaaaaa' no pertenecen a L. Puedo demostrar que aaaa y aaaaaa es deducible utilizando el reg exp per anterior:

aaaa:

a U b U c -> a

ab U ac U b -> cadena vacía

a U b -> a

(aa)* -> aa

tan aaaa

para aaaaaa:

a U b U c -> a

ab U ac U b -> cadena vacía

a U b -> a

(aa)* -> aaaa

así que, aaaaaa

¿Estoy haciendo algo mal? Gracias.

Answer 1

La expresión regular es una concatenación de $a\cup b\cup c$ y $(ab\cup ac\cup b)^*(a\cup b)\cup (aa)^*$ , así que después de tomar $a$ de $a\cup b\cup c$ debe elegir o bien de $(ab\cup ac\cup b)^*$ o de $(aa)^*$ no se pueden utilizar ambas, ya que son alternativas dentro de la expresión $$(ab\cup ac\cup b)^*(a\cup b)\cup (aa)^*\;.$$ (En mi comentario original, ahora eliminado, se me pasó poner entre paréntesis $$(ab\cup ac\cup b)^*(a\cup b)\cup (aa)^*\;,$$ leyendo la expresión como $(a\cup b\cup c)(ab\cup ac\cup b)^*(a\cup b)\cup(aa)^*$ como unión (o disyunción) de dos expresiones y no como concatenación).

Si elige entre $(ab\cup ac\cup b)^*$ claramente no conseguirás todo $a$ por lo que debe elegir entre $(aa)^*$ . Eso te da $2n$ $a$ 's para algunos $n\ge 0$ por lo que, junto con el $a$ de $a\cup b\cup c$ tienes $a^{2n+1}$ . En otras palabras, si se genera una cadena de $a$ contiene necesariamente un número impar de $a$ 's.

También puedes verlo 'multiplicando' la expresión regular original. Se obtiene una unión (o disyunción) de los siguientes términos:

$$\begin{align*} &a(ab\cup ac\cup b)^*a\\ &a(ab\cup ac\cup b)^*b\\ &b(ab\cup ac\cup b)^*a\\ &b(ab\cup ac\cup b)^*b\\ &c(ab\cup ac\cup b)^*a\\ &c(ab\cup ac\cup b)^*b\\ &a(aa)^*\\ &b(aa)^*\\ &c(aa)^* \end{align*}$$

El único de ellos que genera todos $a$ 's es $a(aa)^*$ que siempre genera un número impar de $a$ 's.