Author Topic: Help with coming up with this regular expression.  (Read 5190 times)

0 Members and 1 Guest are viewing this topic.

Offline while1

  • x86
  • Hero Member
  • *****
  • Posts: 1013
    • View Profile
Help with coming up with this regular expression.
« on: November 17, 2007, 06:43:59 pm »
Ok, so I need to figure out the regular expression for this DFA (Deterministic Finite Automata) model, and I've identified the pattern characterized by the DFA... just can't seem put it into the form of a regular expression correctly.

The regular expression accepts any binary string (string of 1's and 0's) that meets the following:

-The number of 0's in the string has to be a multiple of 2 that's greater than or equal to 2.
-The number of 1's in the string has to be a multiple of 3 that's greater than or equal to 3.

Please help.  Thanks.
I tend to edit my topics and replies frequently.

http://www.operationsmile.org

Offline iago

  • Leader
  • Administrator
  • Hero Member
  • *****
  • Posts: 17914
  • Fnord.
    • View Profile
    • SkullSecurity
Re: Help with coming up with this regular expression.
« Reply #1 on: November 17, 2007, 06:48:48 pm »
Ack! That brings back some horrible memories. There's probably a time I could have helped, but not anymore. Sorry. :(

Hmm... I'll think about this

Offline while1

  • x86
  • Hero Member
  • *****
  • Posts: 1013
    • View Profile
Re: Help with coming up with this regular expression.
« Reply #2 on: November 18, 2007, 12:48:41 am »
NEVERMIND DOESNT WORK.
« Last Edit: November 18, 2007, 12:53:50 am by Michael »
I tend to edit my topics and replies frequently.

http://www.operationsmile.org

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Help with coming up with this regular expression.
« Reply #3 on: November 18, 2007, 12:57:28 am »
I don't think regular expressions are the right way to approach this problem.  Any way you do it it's going to be O(n) or worse, so going over the string and keeping two counters seems like a much more efficient solution.  Regular expression engines have a lot of overhead, obviously.

Do you really "need" a regular expression for an assignment or something?

Edit --

NEVERMIND DOESNT WORK.

lol?

Offline iago

  • Leader
  • Administrator
  • Hero Member
  • *****
  • Posts: 17914
  • Fnord.
    • View Profile
    • SkullSecurity
Re: Help with coming up with this regular expression.
« Reply #4 on: November 18, 2007, 01:02:30 am »
Do you really "need" a regular expression for an assignment or something?

Just a guess, but it sounds like a homework assignment to me.

<edit> Not that there's anything wrong with that, I'm happy to help if I could. I'm just saying. :)

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Help with coming up with this regular expression.
« Reply #5 on: November 18, 2007, 01:05:51 am »
Do you really "need" a regular expression for an assignment or something?

Just a guess, but it sounds like a homework assignment to me.

<edit> Not that there's anything wrong with that, I'm happy to help if I could. I'm just saying. :)

Yeah, that's what I figured.

However, I've seen a lot of people that get see a problem, decide on a potential solution and get caught up in it without stopping to consider the alternatives.

Offline while1

  • x86
  • Hero Member
  • *****
  • Posts: 1013
    • View Profile
Re: Help with coming up with this regular expression.
« Reply #6 on: November 18, 2007, 01:07:57 am »
Yeah, it's homework, and it's required to come up with a regular expression for it.

The "NEVERMIND DOESNT WORK" was because I posted an answer that I then realized was wrong.
I tend to edit my topics and replies frequently.

http://www.operationsmile.org

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Help with coming up with this regular expression.
« Reply #7 on: November 18, 2007, 01:19:31 am »
This is nothing more than a glorified hint, really, but maybe it will help?

You could use grammars to represent a binary string with an even number of zeros like this...

S = <1><R><1>
R = <1><0><1><0><R>|<1><0><1><0>
1 = "1"|"1"<1>|[tex]\lambda[/tex]
0 = "0"

Which is pretty easily translatable into a regular expression, I guess.  Something like

$1*(1*01*0)+1*^

Offline while1

  • x86
  • Hero Member
  • *****
  • Posts: 1013
    • View Profile
Re: Help with coming up with this regular expression.
« Reply #8 on: November 18, 2007, 01:16:51 pm »
This is nothing more than a glorified hint, really, but maybe it will help?

You could use grammars to represent a binary string with an even number of zeros like this...

S = <1><R><1>
R = <1><0><1><0><R>|<1><0><1><0>
1 = "1"|"1"<1>|[tex]\lambda[/tex]
0 = "0"

Which is pretty easily translatable into a regular expression, I guess.  Something like

$1*(1*01*0)+1*^

I guess I didn't note that valid binary strings can begin with a sequence of 0's as long as they meet the requirement that the number of 0s is a multiple of 2 [tex]\geq[/tex] 2.  Since according to the diagram of the DFA such a binary string is acceptable.  Note, that the first part of the HW was to code the DFA- and that was easy.  Second part is writing it's regular expression.

Didn't really look through your answer completely, but going to now give a crack at it using a grammar- we did grammars and parse trees way back earlier in the semester for programming languages, and see if I can get it.  Thanks for the idea.

EDIT:  The LaTeX BBCode tag is awesome!

EDIT2:  Looking at your grammar, does the lambda indicate recursion?  I don't think we learned that notation when learning grammars (didn't go too indepth into grammars), but I'm guessing it's related to recursion?
« Last Edit: November 18, 2007, 02:12:55 pm by Michael »
I tend to edit my topics and replies frequently.

http://www.operationsmile.org

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Help with coming up with this regular expression.
« Reply #9 on: November 18, 2007, 03:26:47 pm »
I guess I didn't note that valid binary strings can begin with a sequence of 0's as long as they meet the requirement that the number of 0s is a multiple of 2 [tex]\geq[/tex] 2.  Since according to the diagram of the DFA such a binary string is acceptable.  Note, that the first part of the HW was to code the DFA- and that was easy.  Second part is writing it's regular expression.

Didn't really look through your answer completely, but going to now give a crack at it using a grammar- we did grammars and parse trees way back earlier in the semester for programming languages, and see if I can get it.  Thanks for the idea.

EDIT:  The LaTeX BBCode tag is awesome!

EDIT2:  Looking at your grammar, does the lambda indicate recursion?  I don't think we learned that notation when learning grammars (didn't go too indepth into grammars), but I'm guessing it's related to recursion?

[tex]\lambda[/tex] indicates the empty string.  However, the definitions of most of those grammars are recursive.  The empty string is a way to escape the grammar for <1> without being required to include a literal "1".

The regex I gave you will match any binary string containing an even number of zeros, I'm pretty sure.  Notice that "*" indicates "repeated 0 or more times".  I'm pretty sure it would be reasonably easy to extend it to include the other specification.

Offline Camel

  • Hero Member
  • *****
  • Posts: 1703
    • View Profile
    • BNU Bot
Re: Help with coming up with this regular expression.
« Reply #10 on: November 18, 2007, 04:20:01 pm »
Sidoh: your grammar is clever, but it won't work for keeping a multiple of three ones. A regular expression is a completely in appropriate solution, although it may be possible.

It would certainly be possible to validate the string with three regex's: one to validate it's only zeroes and ones, one to count the zeroes, and one to count the ones:

$(0*1*)+^
$([^0]*0{1}[^0]*0{1})+[^0]*^
$([^1]*1{1}[^1]*1{1}[^1]*1{1})+[^1]*^

<Camel> i said what what
<Blaze> in the butt
<Camel> you want to do it in my butt?
<Blaze> in my butt
<Camel> let's do it in the butt
<Blaze> Okay!

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Help with coming up with this regular expression.
« Reply #11 on: November 18, 2007, 04:25:21 pm »
Sidoh: your grammar is clever, but it won't work for keeping a multiple of three ones. A regular expression is a completely in appropriate solution, although it may be possible.

It would certainly be possible to validate the string with three regex's: one to validate it's only zeroes and ones, one to count the zeroes, and one to count the ones:

$(0*1*)+^
$([^0]*0{1}[^0]*0{1})+[^0]*^
$([^1]*1{1}[^1]*1{1}[^1]*1{1})+[^1]*^

I was trying to leave the answer abstract so he could come up with a solution himself! :(

I agree, though.  A regular expression is a pretty silly solution.  However, it does force you to think in terms of grammars (at least on some level), which I suppose is important in a setting like this.

Offline Camel

  • Hero Member
  • *****
  • Posts: 1703
    • View Profile
    • BNU Bot
Re: Help with coming up with this regular expression.
« Reply #12 on: November 18, 2007, 08:06:08 pm »
While a properly designed question does encourage that kind of critical thinking, don't be mistaken: not every grammar can be expressed as a finite regular expression. There are many examples of complex recursive grammars that are believed to be impossible to express as a single regular expression floating around on the internet.

Regular expressions are designed to match simple patterns. Of course they can match complex grammars, but it's often unwise to opt for regular expressions in these cases. This problem is a perfect example of where regular expressions fall short.

<Camel> i said what what
<Blaze> in the butt
<Camel> you want to do it in my butt?
<Blaze> in my butt
<Camel> let's do it in the butt
<Blaze> Okay!

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Help with coming up with this regular expression.
« Reply #13 on: November 19, 2007, 12:36:42 am »
While a properly designed question does encourage that kind of critical thinking, don't be mistaken: not every grammar can be expressed as a finite regular expression. There are many examples of complex recursive grammars that are believed to be impossible to express as a single regular expression floating around on the internet.

Regular expressions are designed to match simple patterns. Of course they can match complex grammars, but it's often unwise to opt for regular expressions in these cases. This problem is a perfect example of where regular expressions fall short.

I agree with everything you said here, but it seems to me that you're implying I said things that I didn't.  :)

Offline Camel

  • Hero Member
  • *****
  • Posts: 1703
    • View Profile
    • BNU Bot
Re: Help with coming up with this regular expression.
« Reply #14 on: November 20, 2007, 07:59:23 pm »
Actually, I was trying to imply that I believe this problem belongs to the set that can not be expressed with a single regular expression. I don't want to jump to that conclusion, however, since I've already learned that lesson. :P

<Camel> i said what what
<Blaze> in the butt
<Camel> you want to do it in my butt?
<Blaze> in my butt
<Camel> let's do it in the butt
<Blaze> Okay!