Mike Haertel <haertel@ichips.intel.com> wrote:
> I strongly recommend that you abandon any attempt to do intersection
> or complement of regular languages. The reason is that intersection
> can shorten the length of a regexp by an exponential amount, or
> equivalently, grow the automaton by an expontential amount.
Not really. Complement is trivial if you have the DFA. You just complement
the states. If you have two DFAs M and N, with number of states m and n,
you can do M \cap N by crossing the states. So you end up with mn states.
Of course, you get exponential blow-up when you go from a NDFA to a DFA,
but that's neither complement's nor intersection's fault.
-Kelvin
|