# What language does the regular expression $c^\ast(a \cup (bc^\ast))^\ast$ generate?

Anyone explain what language will be generated by the following regular expression? I know this has some math in it is why I post it here

$$c^\ast(a \cup (bc^\ast))^\ast .$$

Edit [by SN]: Corrected the regular expression from $(c^*(a U (bc^*))^*)$.

-
The $U$ seems to denote "union", so I edited it to $\cup$ in the question. – Srivatsan Sep 23 '11 at 4:17
German. It generates German. – Gunnar Þór Magnússon Sep 23 '11 at 5:10
Yes, I believe it is UNION – Kobojunkie Sep 23 '11 at 12:42

I’m going to assume that $U$ is intended to be union, so that the regular expression is actually $(c^*(a\cup(bc^*))^*)$.

The expression $(bc^*)$ generates strings consisting of a $b$ followed by any number of $c$’s (including none), so $(a\cup(bc^*))$ generates the words $a$, $b$, $bc$, $bcc$, $bccc$, and so on. Starring this allows us to get any finite concatenation of these words, including $\lambda$, the empty word. Let’s consider first the words that can be generated from $(a\cup(bc^*))$ without using any $c$’s. We can get any number of $a$’s in a row and any number of $b$’s in a row, and they can be mixed as we please, so we can get all of $\{a,b\}^*$. What about the words that contain at least one $c$? We can get $c$’s only from $bc^*$, so every string of consecutive $c$’s must be immediately preceded by a $b$. Thus, the words generated by $(a\cup(bc^*))$ can be described as follows: take any word consisting entirely of $a$’s and $b$’s, and optionally insert any number of $c$’s after any of the $b$’s. Finally, the initial $c^*$ in $(c^*(a\cup(bc^*))^*)$ allows any number of $c$’s to be added at the front of the word.

In not quite plain English, then, the language generated by $(c^*(a\cup(bc^*))^*)$ consists of all words $w$ over the alphabet $\{a,b,c\}$ with the following property:

• every $c$ in $w$ is either part of an initial string of $c$’s or part of a string of $c$’s immediately following a $b$.

Equivalently:

• if $w=ucv$ for some words $u$ and $v$, then either $u$ is of the form $c^*$ (empty or a string of $c$’s), or $u$ is of the form $tbc^*$ for some word $t$ ($u$ ends in a $b$ followed by a string of $c$’s).

And if you think about this just a little more, it’s not too hard to realize that it boils down to a very simple description:

• the language consists of all words over $\{a,b,c\}$ in which an $a$ is never immediately followed by a $c$.
-
You mean $(a\cup(bc^*))$ could not generate $ab , abc$ ? – Kobojunkie Sep 23 '11 at 12:41
$\cup$ stands for $or$ operation, therefore $ab$ cann't be generated – com Sep 23 '11 at 17:34