Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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$.
share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.