On Mar 25, 2005, at 11:53 AM, Greg Bacon
<gbacon-85RWSX2tBRuL3ccDcF8u4Q@xxxxxxxxxxxxxxxx> 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
jeff-pnJJyULZxQIdnm+yROfE0A@xxxxxxxxxxxxxxxx
|
