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.

Okay, so I come across a question: What language is represented by this regular expression:

$$(((a*b)b) \cup b)$$

An example given prior to this is: L(anguage) = $\{w | w \in \{0,1\}\}$

L(anguage) = $0*10*010*(10* \cup E)$

I am completely lost with this o.o The only thing i can think of here is... $L = \{ab, b, bb\}$ But that is a wild guess.

share|improve this question
1  
Is '*' the repetition operator? If you're lost, it may be a good way to structure your thoughts to draw an abstract syntax tree for the regular expression and figure out what the languages described by each subexpression is from the leaves upwards. –  Henning Makholm Sep 23 '11 at 15:39
add comment

3 Answers

up vote 1 down vote accepted

You are trying to understand the regular expression $(((a^∗b)b)∪b)$ = $(a^*bb) \cup b)$. If we split this expression up we get two expressions $a^*bb$ and $b$ with the union operator. As you know the union operator is "or", so our expression can be formulated as $a^*bb$ or $b$. So L(Expression) = {w|w $\in a^*bb$ or $w \in b$} ("The language of E, with E our expression, are all strings that are in the language generated by the expression $a^*bb$ or the expression $b$.)

Now the only string that is generated by the expression $b$ is $b$ itself, so we have our first word. Now to look at the expression $a^*bb$, $a^*$ implies zero or more a's and $bb$ just implies two b's. So we can finally define L(E) = {w|w has zero or more a's followed by two b's or w is b}. Example strings are $abb, bb, aaaabb, b, ...$ but not $bbb, ba, ...$. Hope this makes it a bit more clear.

share|improve this answer
add comment

* - zero or more occurrences of followed symbol

UNION - $or$ operation

so regular expression can generate bb, abb, aabb, aaabb, b (because of $or$ operation),...

good brief explanation

Regular expression $baa \in a^*b^*a^*b^*$: is that true or false?

complete topic about regular expressions with many examples

http://www.cs.princeton.edu/courses/archive/spr05/cos126/lectures/18.pdf

share|improve this answer
add comment

You have the regular expression $(((a^*b)b)\cup b)$. The subexpression $(a^*b)$ generates the words $b,ab,aab,aaab$, etc., because $a^*$ generates any string of $a$’s, including none at all. These words can be described in English as the words over the alphabet $\{a,b\}$ that contain exactly one $b$ and have that $b$ at the very end. Alternatively, they are the words that start with any number of $a$’s (including none) and then have a single $b$.

Let’s build up to the next larger subexpression: $((a^*b)b)$ takes any word generated by $(a^*b)$ and tacks a $b$ on the end, so we now get $bb,abb,aabb,aaabb$, etc.; these are the words that start with any number of $a$’s, possibly none, and then have $bb$. Alternatively, they could be described as the words that end in $bb$ and have nothing but $a$’s before that.

The subexpression $b$ on the right of the union of course generates only one word, $b$.

Finally, the union in $(((a^*b)b)\cup b)$ gives you everything generated by $((a^*b)b)$ or by $b$, so you get every word that ends in $bb$ and has nothing but $a$’s before that (if anything), and in addition you get the word $b$.

share|improve this answer
add comment

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.