[algogeeks] Re: help making regular expression
I think a regular expression is just too hard, a CFG might be easier . Let
me know if you have a solution for regular expression
On 3/14/07, Ravi [EMAIL PROTECTED] wrote:
what will be a regular expression(non-UNIXone please) for the set of
languages which have number of 0s divisible by 5 and number of 1s
divisible by 2. The set of alphabets is {0,1}.
Please tell how you arrived at the solution.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Sorting o(n) time
You could try the quick-sort algo with these further modifications : every time you partition the list (assuming ascending) you leave out the entire working for the right hand part iff the size of the left hand part is = m (m is the top m elements that you need). NB : Here left hand part indicates the part to the left of the pivot i.e. right from the beginning of the array. This on an average case should be able to accomplish the task in O(n) time. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: help making regular expression
A DFA is possible I guess which is interesting, see if the following DFA works, since the existence of the DFA relates to the existence of a Regular Expression Describing the language State/Input 01 q00 q10 q01 q10 q20 q11 q20 q30 q21 q30 q40 q31 q40 q00 q41 q01 q11 q00 q11 q21 q10 q21 q31 q20 q31 q41 q30 q41 q01 q40 The final state is q00. In this DFA the first subscript denotes the number of zeros % 5 and the second describes the number of ones % 2 --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: help making regular expression
If the DFA works then it can be converted to a regular expression using standard techniques like the one described in http://www.cs.colostate.edu/~whitley/CS301/L3.pdf --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: help making regular expression
On 3/15/07, Ravi [EMAIL PROTECTED] wrote:
what will be a regular expression(non-UNIX one please) for the set of
languages which have number of 0s divisible by 5 and number of 1s
divisible by 2. The set of alphabets is {0,1}.
The following is based on `Parallel Regular Expressions'. If I
remember correctly, PREs have been proven to be equivalent to the set
of `Regular Languages'.
So assuming you're equipped with that,
(a) 0s div by 5 --- (0)* -- R_a (Regular expression a)
(b) 1s div by 2 --- (11)* -- R_b
Now PREs define an operator called `shuffle' which basically causes an
`interleave' of strings from both languages.
So based on whatever the notation is for writing down an interleave,
the required PRE will be SHUFFLE(R_a, R_b).
For more information on Parallel Regular Expressions, their
equivalence to Regular Languages refer to
www.cct.lsu.edu/personal/estrabd/papers/paper333final.pdf
PREs basically provide this additional tool of shuffling, which much
like non-determinism (in finite state machines) turns out to NOT
provide any additional power in accepting languages.
--
Regards,
Rajiv Mathews
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
