Monday, November 10, 2008

Even Zeros and Odd Ones

This question left in today's lecture is interesting, said need to find a regular expression by using the set (0,1) to produce even zeros and odd ones. The graph which is drawn in the lectur can slove this question easy. Image there is four staes say s0, top left, s1, top right, s2, bottom left, s3 bottom right. Obvious we know that:
s0 and s1 represent even ones, while s2 and s3 represents odd ones.
s0 and s2 represent even zeros, while s1 and s3 represents odd zeros.
Here our question becomes the way that travesal from s0 to s2 where is our destination that represented by even zeros and odd ones.
After all the setup above, we can start our travesal. One thing need to point out is there are many self-circle(?what is the official name for this?) should be considered, like s0 to s1 then back to s0.
Ok, here we go. Start from s0.
1. We can directly go from s0 to s2 where is our destination, done! Easy case, may called base case??
2. From s0 to s1 to s3 to s2, which is the clcokwise traversal. Thus we can get the expression like 010. However, we can have s0 to s2, not stop here, but go to s3 and then back to s2. There are many cases need to consider, keep in mind that s3 can go back and forth with s1 and s2 many times. Likely wise, we can have a countclockwise traversal, from s0 to s2, it is a duplicate expression from where we discussed above. Thus we can conclude that 1+(01+10)(11+00)*0 is our expression.
3. The above expression just from s0 to s2, we know that there are a lot of ways from s0 to anywhere states and come back to s0 again, this situation should concatenate with the expression above. From s0 to s1 back to s0 will gives us 00, so to s2 back to s1 will gives us 11. More states now s0 to s1 to s3 back to s1 will give us (01+10)(00+11)*(10+01), so or then up and concatenate with first expression gives us.
(00+11+(01+10)(00+11)*(10+01))*(1+(01+10)(11+00)*+0)

No comments: