a is followed immediately by bb. i want some help here .

thanks

Solved

Posted on 2008-11-04

hi guys i want to solve this question .

Q : Give Regular Expressions for the following languages (L1, L2, L3) defined over the alphabet {a, b}

L1 = The set of strings in which every a is followed immediately by bb.

L2 = The set of strings of a's and b's whose number of a's is divisible by 5.

L3 = The set of strings of a's and b's whose 3rd symbol from the right is b.

Q : Give Regular Expressions for the following languages (L1, L2, L3) defined over the alphabet {a, b}

L1 = The set of strings in which every a is followed immediately by bb.

L2 = The set of strings of a's and b's whose number of a's is divisible by 5.

L3 = The set of strings of a's and b's whose 3rd symbol from the right is b.

12 Comments

a is followed immediately by bb. i want some help here .

thanks

A string might be .*abb.* where the dot-stars represent anything. BUT the first dot-star CANNOT be an a, so ot must be b. This makes the string b*abb.*. Now the second dot-star can of course contain b but it could also contain a followed by bb. But that is the same as the original string, so the solution is b*aab repeated at least one time, ie: (b*aab)+

NOw please try doing the second one. Hint: a string that contains five a's is (a)5, so you just need to pad it out with b's.

Indeed, this is not a confusing assignment at all. However, I will coach you to answer it.

First, consider the language (L) defined over the alphabet {

This results in all stings built up by interleaving sequences of

Now, consider the three special cases (L1, L2, L3) of (L). We will take them in the order (L1, L3, L2):

L1:

L3:

L2:

I think that you'r mistaken in both (L1) solution and (L2) hints!

Kindly, read the Question once again.

SyfAldeen: You're quite right. I wasn't really trying to post a solution, that is why the first part of the sentence is correct, but the (b*aab)+ is incorrect. As regards to L3 the (a)5 being "padded out with b's" is correct, nute once again we get back to the principle of repetition.

I appreciate your reply. However, consider these points:

- Regarding (L1), it's not
**aab**at all, it's**abb**. - "
*repeated at least one time*" is not correct. The constraint states that every**a**is followed by**bb**. Nothing indicated that*at least*one**a**must also exist. - Your expression does not accept strings like
**b**,**bb**,**abbb**,**...**event if it's corrected to (**b*****abb**)*. ie any string that contains**b**not followed by (**abb**or another**b**). - Regarding (L2), expressing the five
**a**'s as (**a**)5 is misleading as it reflects that every five**a**'s are expected to be consecutive. It should be something like "".**aaaaa**interleaved with**b**'s

It is a pity one cannot edit one's posts, then a slight slip from abb to aab would have been easy to correct. This is something I have complained about to E-E time and time again.

The repeated at least one time refers to the (xxxx)+ construct.

>>Your expression does not accept strings like b,bb,abbb,..

This is wrong. Strings like b and bb are not to be accepted. I acknoweldged that abbb etc was not accepted. That is simply (b*aabb*)+

I don't think that (a)5 is misleading, since it is a start. It would be changed to ((a)5)+ to accept more than one sequence and then one would simply pad it out with b*s. What's the problem? In fact if anything "aaaaa interleaved with b's" suggests that the string should start with an a.

Once again, an empty string is a correct (L1) string. Yes, in an empty string

Once again, you mistyped the expression and wrote (

Finally, (L2) does not require

ozo,

Yes, they are.

When we define (L1) as the set of strings in which

Can you see

BigRat,ozo,

Anyway, I think that we are making a good coaching for jamie_2008 by this interesting discussion ;-). Therefore, I think it may be the time to solve (L1):

(

You can verify my answer by testing the RegEx or you can check this example:

Discrete Mathematics Published by Allied Publishers, 1996

I'll be waiting for jamie_2008 to solve the (L2,L3) and post his solution.

That is dependant on how exactly you view the question. Strings not containing a are in fact what is known as a trivial solution. The solution of (b|abb)* is without trivial solutions (b|abb)+. Now to arrive at (b|abb)+ you'd first need to arrive at (b*abbb*)+ and factor out the b*. That is why (a5)+ is NOT misleading - it is the starting point. So far you have only offered solutions with explainations on how they work and NOT a method for proceeding to them.

First, this is not a trivial solution. In addition, you cannot simply consider one solution trivial yourself. However, if it's a trivial solution, then you can't just omit it!

Trivial (mathematics) - Wikipedia, the free encyclopedia

If you noticed the example of the Discrete Mathematics book, (

Second, what factoring are you talking about?

Distributivity - Wikipedia, the free encyclopedia.

If you are looking for a derivation from your answer to the right answer, see below.

Third, indeed, I've already showed how to find the answer using logical thinking. In my first post, I showed that the language (L) defined over the alphabet {

Finally, let us postpone talking about (L2) until jamie_2008 shows up and I'll prove that (

Anyway, I am happy that I have a chance to benefit from your experiences.

```
(b*abbb*)+ --( Correct it first to )-->
(b*abbb*)* --( Correct it again to )-->
(b*(abb)*b*)* --( Since (R*S*)*=(R|S)* )-->
(b|abb|b)* --( Rearrange )-->
(b|b|abb)* --( Since R|R=R )-->
(b|abb)*
```

By clicking you are agreeing to Experts Exchange's Terms of Use.

Title | # Comments | Views | Activity |
---|---|---|---|

Volume Calculation | 14 | 34 | |

Regex Balancing Group | 30 | 60 | |

Discrete Probability | 2 | 40 | |

Geomentry-Fundamental concepts | 6 | 32 |

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**12** Experts available now in Live!