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

Jeffrey M.Vinocur <[email protected]> writes:

> 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?

No, you haven't been following the thread very closely - it's the
integers evenly divisible by N, which set is not finite.

However, I think that it might be proveable that any regular language
is still a regular language when you reverse all the strings in that
language.  A formal proof probably relies on the Myhill-Nerode
theorem, but an informal proof has already been sketched out here,
using some hand-waving definitions of NDFAs as circles and arrows.