Programming challenge: wildcard exclusion in cartesian products

[funkyj]

Chris F Clark wrote:
> Yes, there is literature on the generating side of the regular
> expression/FSM model.  In fact, the matching problem and the
> generating problems are exactly equivalent.  A slight variation of the
> definition of how a matcher works, turns it into a generator and vice
> versa.  To directly generate (rather than match) from an FSM, one
> simply does a walk (e.g. depth first search or breath first search)
> over the machine writing out (rather than matching) the symbols used
> as labels.  Thus, all the theorems about matching apply to generating
> and also in reverse.

 If the language is Sigma* (rather than Sigma^n in the original post)
then doing a depth first search over the FSM requires a stack to
maintain context, right?  I find it interesting that you suggest a PDA
(push down automata) is required to enumerate the language accepted by
an FSM since PDAs are strongly associated with CFGs (context free
grammars).  Does it follow then that a Turing machine is required to
enumerate the language defined by a CFG?  (that was a joke, I think).


> It is worth noting the regular languages
> are closed under the difference operator, so that resulting language
> from substracting one regular expression from another is still a
> regular language,

I was pretty sure this was the case but it has been more than a decade
since I studied computational models in school so I wasn't absolutely
certain.  While I do remember homework that called for creating FSMs
that accepted languages defined by a regexp, I don't recall having
solved the "enumeration" problem.

Your clear and concise comments did a nice job of jogging my memory.

  ===

It seems to me that the purpose of the original challenge was to
compare how different languages implement the solution to the problem.
For such a well understood problem as this the goal of the challenge
(to contrast the languages) is best served when participants have a
good understanding of the 'state of the art' abstract solutions (e.g.
using a stack to traverse a FSM in DFS fashion).