?
Solved

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

Posted on 2008-11-04
13
Medium Priority
?
781 Views
Last Modified: 2012-05-05
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.
0
Comment
Question by:jamie_2008
12 Comments
 

Author Comment

by:jamie_2008
ID: 22878298
yes , this is my assignemnt , i m confused in making this .

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

thanks
0
 
LVL 51

Expert Comment

by:ahoffmann
ID: 22885671
please provide what you have done so far
0
 
LVL 27

Expert Comment

by:BigRat
ID: 22885703
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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 4

Accepted Solution

by:
SyfAldeen earned 1800 total points
ID: 22886418
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
 
LVL 4

Expert Comment

by:SyfAldeen
ID: 22887211
BigRat,
I think that you'r mistaken in both (L1) solution and (L2) hints!
Kindly, read the Question once again.
0
 
LVL 27

Expert Comment

by:BigRat
ID: 22887669
>>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
 
LVL 4

Expert Comment

by:SyfAldeen
ID: 22888156
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
 
LVL 27

Assisted Solution

by:BigRat
BigRat earned 200 total points
ID: 22888395
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
 
LVL 85

Expert Comment

by:ozo
ID: 22888724
> strings like b,bb,abbb,..
in those strings, every a is followed immediately by bb
0
 
LVL 4

Assisted Solution

by:SyfAldeen
SyfAldeen earned 1800 total points
ID: 22890721
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
 
LVL 27

Expert Comment

by:BigRat
ID: 22893574
>>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
 
LVL 4

Expert Comment

by:SyfAldeen
ID: 22894425
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

Featured Post

New feature and membership benefit!

New feature! Upgrade and increase expert visibility of your issues with Priority Questions.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

As most anyone who uses or has come across them can attest to, regular expressions (regex) are a complicated bit of magic. Packed so succinctly within their cryptic syntax lies a great deal of power. It's not the "take over the world" kind of power,…
Foreword (May 2015) This web page has appeared at Google.  It's definitely worth considering! https://www.google.com/about/careers/students/guide-to-technical-development.html How to Know You are Making a Difference at EE In August, 2013, one …
Learn how to match and substitute tagged data using PHP regular expressions. Demonstrated on Windows 7, but also applies to other operating systems. Demonstrated technique applies to PHP (all versions) and Firefox, but very similar techniques will w…
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Suggested Courses

850 members asked questions and received personalized solutions in the past 7 days.

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

Join & Ask a Question