Clan x86
Technical (Development, Security, etc.) => General Programming => Topic started by: while1 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.
-
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
-
NEVERMIND DOESNT WORK.
-
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?
-
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. :)
-
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.
-
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.
-
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*^
-
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 (http://images.mikecompscigeek.com/dfa.jpg) 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?
-
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 (http://images.mikecompscigeek.com/dfa.jpg) 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.
-
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]*^
-
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.
-
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.
-
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. :)
-
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