Re: [SPOILER] Perl 'Hard' Quiz of the Week #2005-03-22

On Mar 25, 2005, at 11:53 AM, Greg Bacon <[email protected]> wrote:

> [...] got stuck when
> I realized all powers of two would land in the same state, for
> instance.  I even tried to think of a way to use the pumping lemma
> to show that the reversed language isn't regular.

I haven't been following this thread very closely, but by "reversed 
language" you still mean the set of strings encoding (in whatever 
representation) the integers that evenly divide some N, right?

If so, then it doesn't matter what the representation is -- even 
something as absurd as binary digits alternately taken from the most- 
and least-significant ends of the number -- the language in question 
only contains a finite number of strings.  (Clearly no number larger 
than N will divide evenly, which gives a crude upper bound.)

All finite languages are regular.  I agree that it's not intuitive what 
the equivalence  classes "mean" (which I believe is what gave you 
pause), but they must exist.  And this means that, if no obvious 
generation algorithm springs to mind, you can simply brute-force the 
finite DFA (and then minimize it if you like).


-- 
Jeffrey M. Vinocur
[email protected]