0
$\begingroup$

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

  • 0
    Yes, I believe it is UNION2011-09-23

1 Answers 1

2

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$.
  • 0
    $\cup $ stands for $or$ operation, therefore $ab$ cann't be generated2011-09-23