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). -- http://mail.python.org/mailman/listinfo/python-list
