wu :: forums « wu :: forums - RegEx: divisible by 3 » Welcome, Guest. Please Login or Register. Nov 29th, 2024, 9:56pm

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    cs (Moderators: ThudnBlunder, Grimbal, william wu, Eigenray, SMQ, Icarus, towr)    RegEx: divisible by 3 « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: RegEx: divisible by 3  (Read 4240 times) william wu wu::riddles Administrator     Gender: Posts: 1291 RegEx: divisible by 3   « on: Feb 26th, 2003, 3:28am » Quote Modify Construct a finite state machine (or equivalently, write a regular expression) which accepts all strings over the alphabet {0,1} which are divisible by 3 when interpreted in binary.       Note 1: There is a one-to-one correspondence between Regular Expressions and Finite State Machines. If you think you can solve the problem more easily by writing a regular expression, go ahead. However, a state machine approach will probably be more intuitive, and the solution will be more understandable.   Note 2: When scanned from left to right, the string is interpreted as moving from most significant bit to least significant, as expected. IP Logged [ wu ] : http://wuriddles.com / http://forums.wuriddles.com towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: RegEx: divisible by 3   « Reply #1 on: Feb 26th, 2003, 8:51am » Quote Modify .. once a prefix is divisible by three the number is divisible by three if the rest is divisible by three (so you can then ignore the prefix).   And for the rest you can just work mod 3.   So three states a0, a1 and a2, and transitions a0 -0-> a0 a0 -1-> a1 a1 -0-> a2 a1 -1-> a0 a2 -0-> a1 a2 -1-> a2   a0 is the starting state, and the only end state .. « Last Edit: Feb 26th, 2003, 8:52am by towr » IP Logged Wikipedia, Google, Mathworld, Integer sequence DB towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: RegEx: divisible by 3   « Reply #2 on: Feb 26th, 2003, 9:13am » Quote Modify regular expression: ... {0, [1, [0, 1*, 0]*,1]}* ... Finite State Machine (klick here) « Last Edit: Feb 26th, 2003, 9:16am by towr » IP Logged Wikipedia, Google, Mathworld, Integer sequence DB Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board