Why no RE match of A AND B?

[Tim Peters]

[Andrew Koenig]
> Because in general, the intersection of two regular expressions is not
> a regular expression, in the sense that it cannot generally be represented
> by a regular grammar or parsed efficiently by a finite automaton.

Give that a little more thought.  If you have DFAs for regular languages L
and M, the intersection corresponds to running them both in lockstep, where
an accepting state of the combined DFA is hit whenever you land in
acceptings states for both of the original DFAs.  This can be formalized
easily enough be constructing a new DFA whose states are the cross-product
of the original DFAs' states -- then the rest is obvious <wink>.