Regular expression required

Thread Starter

zulfi100

Joined Jun 7, 2012
629
Hi,

Somebody please guide me what would be the solution for the following:

Give a regular expression for L={a^n b^m |n≥ 1, m ≥1, nm≥3}

I have come with the following solution.

a(a)* . bbb(b)*

Zulfi.
 

djsfantasi

Joined Apr 11, 2010
5,841
Hi,

Somebody please guide me what would be the solution for the following:

Give a regular expression for L={a^n b^m |n≥ 1, m ≥1, nm≥3}

I have come with the following solution.

a(a)* . bbb(b)*

Zulfi.
Why do you have “bbb(“? I’m guessing you’re trying to satisfy nm≥3.

But will your regex match “aaab”? Should it?

And will the dot operator do what you want? Let’s try“aaaXbb”? Is that valid? Will it pass your regex expression?

so depending on your answers to my questions, do you think your answer is correct. Maybe it is; maybe not.

What would you change, if anything?
 
Last edited:

Thread Starter

zulfi100

Joined Jun 7, 2012
629
Why do you have “bbb(“? I’m guessing you’re trying to satisfy nm≥3.

But will your regex match “aaab”? Should it?

And will the dot operator do what you want? Let’s try“aaaXbb”? Is that valid? Will it pass your regex expression?

so depending on your answers to my questions, do you think your answer is correct. Maybe it is; maybe not.

What would you change, if anything?
Hi,
Actually there are 3 cases:
(a(a)* . bbb(b)*) + (aaa(a)* . b(b)*) + (aa(a)*. bb(b)*))

Please tell me your solution.

Zulfi.
 

djsfantasi

Joined Apr 11, 2010
5,841
I’m not going to tell you my solution. Homework Help is NOT Homework Dine for you.

You are getting the idea, but I don’t agree with your last answer. I’m not sure what regex engine you’re using but it’s not the syntax I’d use.

First, Ive asked twice. What does the dot operation do in your regex? This is important because I’m very sure it’s not what you think. Look at me reply? And explain what you’re doing and justify why you have it! Otherwise, I can’t help you.

I want you to explain why the phrase
“aa(a)* b(b)*” is necessary?
 

WBahn

Joined Mar 31, 2012
24,974
Hi,

Somebody please guide me what would be the solution for the following:

Give a regular expression for L={a^n b^m |n≥ 1, m ≥1, nm≥3}

I have come with the following solution.

a(a)* . bbb(b)*

Zulfi.
What is your dot operator? Concatenation? Why are you using it in some places but not others? What's the difference between

a(a)* . bbb(b)*

and just

a(a)*bbb(b)*

Are you just trying to make it more readable or obvious? If so, that's perfectly reasonable.

Can your solution generate "aaaaab" or "aabb" ?
 

djsfantasi

Joined Apr 11, 2010
5,841
What is your dot operator? Concatenation? Why are you using it in some places but not others? What's the difference between

a(a)* . bbb(b)*

and just

a(a)*bbb(b)*

Are you just trying to make it more readable or obvious? If so, that's perfectly reasonable.

Can your solution generate "aaaaab" or "aabb" ?
I’ve asked several times. IMHO, he doesn’t know
 

WBahn

Joined Mar 31, 2012
24,974
I’m not going to tell you my solution. Homework Help is NOT Homework Dine for you.

You are getting the idea, but I don’t agree with your last answer. I’m not sure what regex engine you’re using but it’s not the syntax I’d use.

First, Ive asked twice. What does the dot operation do in your regex? This is important because I’m very sure it’s not what you think. Look at me reply? And explain what you’re doing and justify why you have it! Otherwise, I can’t help you.

I want you to explain why the phrase
“aa(a)* b(b)*” is necessary?
I also want to know, for sure, what the dot operator is. Usually it is used for concatenation (but is a vertically centered unfilled circle most of the time, but in ASCII it is often approximated with a period). Usually for these kinds of problems (i.e., in an automata course) the notation used by regex engines isn't allowed because they are not highly standardized and also often allow you to create expressions that are not truly regular expressions (i.e., the engine is more powerful than a finite automaton).

I don't see where he used the expression "aa(a)* b(b)*" anywhere. That expression would generate strings that are not in the specified language.
 

djsfantasi

Joined Apr 11, 2010
5,841
What is your dot operator? Concatenation? Why are you using it in some places but not others? What's the difference between

a(a)* . bbb(b)*

and just

a(a)*bbb(b)*

Are you just trying to make it more readable or obvious? If so, that's perfectly reasonable.

Can your solution generate "aaaaab" or "aabb" ?
As far as I can recall, the dot operator is NOT concatenation. It is a wildcard operator. So while “aaab” is a valid string with his regex, so is “aaaXb” valid and I DONT think the TS means for that interpretation.
 

WBahn

Joined Mar 31, 2012
24,974
As far as I can recall, the dot operator is NOT concatenation. It is a wildcard operator. So while “aaab” is a valid string with his regex, so is “aaaXb” valid and I DONT think the TS means for that interpretation.
In an automata course there are three defined regular operations: union, concatenation, Kleene star. These are usually represented by {∪,·,*} respectively except that the concatenation is usually an unfilled circle, like ° except not as a subscript. The '+' symbol is also commonly used for union. The star operator is written as a superscript, but the normal asterisk is high enough in most type fonts to be close enough.

A short hand for a wildcard is often ∑ since this is usually used to represent the string alphabet, which as a set defines a language consisting of all one-character strings over that alphabet and hence is a valid regular expression in its own right. A given machine operates over a defined alphabet, so even if the . were meant to be wildcard substitution, it would only apply to that machine's defined alphabet. The regex generators that are out there are more general purpose and operate on a pre-defined alphabet that is much larger than the one defined for almost all automata problems (since the machine complexity explodes rapidly as the size of the alphabet increases).
 

Thread Starter

zulfi100

Joined Jun 7, 2012
629
Hi,
djsfantasi:

Thanks for your time.

Sorry I don't know your back ground. Are you a CS person? Actually I have posted here several questions and at this point "." operator i.e. concatenation is a very HL thing for me. I am trying to know your solution because you said some thing like:
<And will the dot operator do what you want? Let’s try“aaaXbb”? Is that valid? Will it pass your regex expression? >

"X" is not in the question. So I am curious about your solution. Your comment has increased my confusion. Homework help does not mean that you increase some body's confusion by asking questions or by providing some guidelines and then backing off.

Finally this is not my home work.

Zulfi.
 

djsfantasi

Joined Apr 11, 2010
5,841
In an automata course there are three defined regular operations: union, concatenation, Kleene star. These are usually represented by {∪,·,*} respectively except that the concatenation is usually an unfilled circle, like ° except not as a subscript. The '+' symbol is also commonly used for union. The star operator is written as a superscript, but the normal asterisk is high enough in most type fonts to be close enough.

A short hand for a wildcard is often ∑ since this is usually used to represent the string alphabet, which as a set defines a language consisting of all one-character strings over that alphabet and hence is a valid regular expression in its own right. A given machine operates over a defined alphabet, so even if the . were meant to be wildcard substitution, it would only apply to that machine's defined alphabet. The regex generators that are out there are more general purpose and operate on a pre-defined alphabet that is much larger than the one defined for almost all automata problems (since the machine complexity explodes rapidly as the size of the alphabet increases).
So there are some major differences. I have always used + for concatenation. Or NO operator for concatenation or sequence of characters. And the dot operator has always been a wildcard operator. In either case, his regex does not define a valid string.
 

djsfantasi

Joined Apr 11, 2010
5,841
Hi,
djsfantasi:

Thanks for your time.

Sorry I don't know your back ground. Are you a CS person? Actually I have posted here several questions and at this point "." operator i.e. concatenation is a very HL thing for me. I am trying to know your solution because you said some thing like:
<And will the dot operator do what you want? Let’s try“aaaXbb”? Is that valid? Will it pass your regex expression? >

"X" is not in the question. So I am curious about your solution. Your comment has increased my confusion. Homework help does not mean that you increase some body's confusion by asking questions or by providing some guidelines and then backing off.

Finally this is not my home work.

Zulfi.
:p

Yes, my experience is in computer science. My experience spans 50 years. I’ve created new languages. Was an early developer/creator of XML. I have written proprietary SQL engines. I was responsible for the operation of a 24x7x365 e-Commerce web site. I write scripts in java, .NET. BASH, Perl, PHP, and others. Basically, at this point in my life, I can code anything.

The bottom line is that you need to learn a bit more. I am trying to teach you. It’s up to you to listen or not.
 

WBahn

Joined Mar 31, 2012
24,974
So there are some major differences. I have always used + for concatenation. Or NO operator for concatenation or sequence of characters. And the dot operator has always been a wildcard operator. In either case, his regex does not define a valid string.
Omitting the operator is usually interpreted as concatenation in an automata course, too. What do you usually use for union? I'm guessing the pipe symbol?

I think his latest (as far as I can tell) regular expression is fine.

Actually there are 3 cases:
(a(a)* . bbb(b)*) + (aaa(a)* . b(b)*) + (aa(a)*. bb(b)*))
There is an unmatched closing paren at the end, which I will assume should either be removed or matched to an initial open paren at the beginning.

If we remove the . as being concatenation (which he has since confirmed is what he meant) and replace the '+' with '|', the latter of which I think is seldom used for anything other than union, we have

a(a)*bbb(b)* | aaa(a)*b(b)* | aa(a)*bb(b)*

I see this as being the set of strings consisting of one or more 'a's followed by one or more 'b's such that if there is only a single 'a' then there are at least three 'b's and vice-versa while if there are only two 'a's there are at least two 'b's and, again, vice-versa. I think that matches the definition of the language given

Give a regular expression for L={a^n b^m |n≥ 1, m ≥1, nm≥3}
There are many ways to write most regular expressions (with, unfortunately, no standard form). I would have probably written it a bit differently, perhaps something like

L = (a*)a(aa|ab|bb)b(b*)

I just think that makes the essential essence of the language a bit more obvious, but things like that are always highly subjective.

Since that center part is effectively "all two character strings over {a,b} except "ba", I wouldn't be surprised if there isn't a common format for expressing that to many regex engines.
 

djsfantasi

Joined Apr 11, 2010
5,841
Hi,

"X" is not part of the question. So I am curious about your solution. Your comment has increased my confusion. Homework help does not mean that you increase some body's confusion by asking questions or by providing some guidelines and then backing off.

Finally this is not my home work.

Zulfi.
I understands that “X” as a bit bit part of the solution. My point was that your Regex solution allows it to be part of your.soliftihh hhHh. Bj part of your solution.
 
Top