News for hackers. Stuff that matters.
Re:Divisibility by 7 by eru on Saturday October 30, 2010 @11:56PM (#1852446)
The rule in the article can be written as a regular expression.

And in general for every number m and base b you can build a finite automata that gives you x mod m for numbers x expressed as a string of digits in base b. The accepting automaton that accepts in case of x mod 7 = 0 for base 10 is just a special case and gives you the regular expression mentioned above.

I am working on the regular expression for 7. In the meantime, look at this regular expression for divisibility by 3 (http://blog.vkistudios.com/index.cfm/2008/12/30/Regular-Expr...). The author shows his work.

Re:Divisibility by 7 by waterhouse on Sunday October 31, 2010 @12:45AM (#1852504)
If you're interested in deterministic finite automata, you might enjoy the game Manufactoria:

http://www.kongregate.com/games/PleasingFungus/manufactoria

In the game, you deal with robots that come with a tape of binary digits (red and blue dots), and you can build a maze using conveyer belts, branch points (which read a dot from the front of the robot's tape), and things that write dots to the end of the tape. You have tasks to fulfill; they start with easy things like "Accept robots with no red dots", then "Accept robots with the same number of red and blue dots", then "Reverse the input string" (that one is unpleasantly hard), and so on.

In particular, there are some user-submitted levels, and one asks, "Accept if the input number is congruent to 3 mod 7." (Input string is interpreted as a binary number, read left-to-right normally, with blue = 1 and red = 0.) I have a pretty nice solution to that one.

Re:Divisibility by 7 by eru on Tuesday November 02, 2010 @06:03PM (#1862580)
Thanks. I tried it. The biggest challenge seems to be to make your layout planar.