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 --- (00000)* --> 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 [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
