Programming challenge: wildcard exclusion in cartesian products

funkyj funkyj at
Tue Mar 28 19:32:18 CEST 2006

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).

More information about the Python-list mailing list