3 ms·
That's true, but it is actually possible to construct true regular expressions that check if a binary string of digits is divisible by an arbitrary integer. Ob
by jlarocco 10y ago
That's true, but it is actually possible to construct true regular expressions that check if a binary string of digits is divisible by an arbitrary integer. Obviously not the quickest or most intuitive way to do it, though.
There's an interesting book that covers some unusual aspects of automata and regular expressions: https://www.amazon.com/Finite-Automata-Regular-Expressions-Solutions/dp/1887187162/ https://www.amazon.com/Finite-Automata-Regular-Expressions-S...
- Chinjut 10y agoSure, for a fixed arbitrary integer M. (Supposing the input is fed in in big-endian order, you just keep track of the remainder modulo M as each new bit comes in, updating it by turning r into (r * 2 + new bit) mod M. Since this only requires finite state, it is regular). But that won't get you a primality checker. You can't get a primality checker. Primes don't comprise a regular language, neither in unary nor in any nontrivial base.
- deleted 10y ago[deleted]
- jayshua 10y agoWhat do you mean by "non trivial base?"
- Chinjut 10y agoOh, just as opposed to unary. Writing numbers in the ordinary way in any ordinary base, which is to say, bases greater than 1; base 2, base 3, base ten, whatever.
- jerf 10y agoIt's worth pointing out that we are talking about representing numbers in unary, though. Or even more directly, plain ol' string length since the RE under discussion doesn't even care what symbols you are using, so "11111" = "abcde" under this RE.