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

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.
jamie_2008Asked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

jamie_2008Author Commented:
yes , this is my assignemnt , i m confused in making this .

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

thanks
0
ahoffmannCommented:
please provide what you have done so far
0
BigRatCommented:
Well the minimum string must be abb (an a followed by two b's)

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.
0
Discover the Answer to Productive IT

Discover app within WatchGuard's Wi-Fi Cloud helps you optimize W-Fi user experience with the most complete set of visibility, troubleshooting, and network health features. Quickly pinpointing network problems will lead to more happy users and most importantly, productive IT.

SyfAldeenCommented:
jamie_2008,
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 {a, b}:- (a|b)*
This results in all stings built up by interleaving sequences of a's and b's.

Now, consider the three special cases (L1, L2, L3) of (L). We will take them in the order (L1, L3, L2):
L1:
The set of strings in which every a is followed immediately by bb.
This means that a cannot appear alone. It must be followed by bb. This means that (L1) includes only stings built up by interleaving sequences of abb's and b's.
L3:
The set of strings of a's and b's whose 3rd symbol from the right is b.
This means that its the same as (L) with one more constraint; the last three characters must be b followed by (a or b) followed by (a or b).
L2:
The set of strings of a's and b's whose number of a's is divisible by 5.
This is a bit challenging. Therefore, it'd be better to reduce the problem to a simpler one. Let's consider the language (L2') of all strings containing only 5 a's and any number of b's. Note that between any two a's there may be zero or more b's. The RegEx of (L2) will be simply the same as (L2') extended by the asterisk *.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
SyfAldeenCommented:
BigRat,
I think that you'r mistaken in both (L1) solution and (L2) hints!
Kindly, read the Question once again.
0
BigRatCommented:
>>But that is the same as the original string, so the solution is b*aab repeated at least one time, ie: (b*aab)+

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.
0
SyfAldeenCommented:
BigRat,
I appreciate your reply. However, consider these points:
  1. Regarding (L1), it's not aab at all, it's abb.
  2. "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.
  3. 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).
  4. 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".
Regards
0
BigRatCommented:
SyfAldeen:

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.
0
ozoCommented:
> strings like b,bb,abbb,..
in those strings, every a is followed immediately by bb
0
SyfAldeenCommented:
BigRat,
Once again, an empty string is a correct (L1) string. Yes, in an empty string every a is followed immediately by bb. Read my reply to ozo below. Therefore, at least one time is not correct.
Once again, you mistyped the expression and wrote (b*aabb*)+ while you mean (b*abbb*)+ which is not correct either! See the correct answer below.
Finally, (L2) does not require a's to be consecutive. Therefore b,bb,bbb,bbbb,bababababab,aaaaabaaaaa,aababaa,baaaaab are strings of (L2). This is what I mean. Therefore, using (a)5 is misleading as I said before.
ozo,
Yes, they are.
When we define (L1) as the set of strings in which every a is followed immediately by bb. This does not imply that the sting must contain a. In other words, a string in which not (every a is followed immediately by bb) is not (L1).
Can you see a not followed by bb in the strings b,bb,abbb. It's clear that every a in these strings is followed by bb. Therefore, these strings are (L1) and must be accepted.
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):
(b|abb)*
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.
0
BigRatCommented:
>>This does not imply that the sting must contain a.

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.
0
SyfAldeenCommented:
BigRat,
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 also refers to solutions to an equation that have a very simple structure, but for the sake of completeness cannot be omitted. These solutions are called the trivial solution."
Trivial (mathematics) - Wikipedia, the free encyclopedia

If you noticed the example of the Discrete Mathematics book, (1+011)* -> (b|abb)*, the author did not consider any solution trivial even for the empty string (/\).
Second, what factoring are you talking about? b*abbb* is a single term and single operation (concatenation)! To factor/distribute there must be more than one term and two binary operations. For example abb*|cbb* can be rewritten as (a|c)bb* by factoring out bb*.
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 {a, b} is (a|b)* or stings built up by interleaving sequences of a's and b's. When (L1) includes only stings built up by interleaving sequences of abb's and b's it becomes (abb|b)* by using abb in place of a. In addition, I provided the link to the book for mathematical derivation.
Finally, let us postpone talking about (L2) until jamie_2008 shows up and I'll prove that (a)5 does not have any relation to the solution nor the 'method for proceeding to' it.
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)*

Open in new window

0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Regular Expressions

From novice to tech pro — start learning today.