Programming challenge: wildcard exclusion in cartesian products
funkyj
funkyj at gmail.com
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