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^*))^*)$.
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^*))^*)$.
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:
Equivalently:
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: