Programming challenge: wildcard exclusion in cartesian products

[Dirk Thierbach]

wkehowski at cox.net <wkehowski at cox.net> wrote:
> Call a wc 'free' if it satisfies the propery that every letter 'a' in
> it appears only in the form '*a*', and 'anchored' otherwise. 

Would '*ab*' be free or anchored?

> What if all wc's are free? How does this affect the DFA?

I don't know. The important point here is the interaction of all
the wc's. I don't think properties like this do reduce the complexity
of interaction in an obvious way.

> Does it minimize nontrivially?

I am not sure what you mean by this. Every DFA minimizes to some
other DFA, which is unique up to renaming of states. Now the
question is if that minimization reduces the complexity enough
to be noticeable (maybe that's what you mean by "nontrivially").
In general, I don't think one can say much about that without
looking at concrete examples.

- Dirk