How about:
/(cat|dog)(?:\W+\w+){0,3}?\W+(?!\1)(cat|dog)/
Explanation:
The regular expression:
(?-imsx:(cat|dog)(?:\W+\w+){0,3}?\W+(?!\1)(cat|dog))
matches as follows:
NODE EXPLANATION
----------------------------------------------------------------------
(?-imsx: group, but do not capture (case-sensitive)
(with ^ and $ matching normally) (with . not
matching \n) (matching whitespace and #
normally):
----------------------------------------------------------------------
( group and capture to \1:
----------------------------------------------------------------------
cat 'cat'
----------------------------------------------------------------------
| OR
----------------------------------------------------------------------
dog 'dog'
----------------------------------------------------------------------
) end of \1
----------------------------------------------------------------------
(?: group, but do not capture (between 0 and 3
times (matching the least amount
possible)):
----------------------------------------------------------------------
\W+ non-word characters (all but a-z, A-Z,
0-9, _) (1 or more times (matching the
most amount possible))
----------------------------------------------------------------------
\w+ word characters (a-z, A-Z, 0-9, _) (1 or
more times (matching the most amount
possible))
----------------------------------------------------------------------
){0,3}? end of grouping
----------------------------------------------------------------------
\W+ non-word characters (all but a-z, A-Z, 0-
9, _) (1 or more times (matching the most
amount possible))
----------------------------------------------------------------------
(?! look ahead to see if there is not:
----------------------------------------------------------------------
\1 what was matched by capture \1
----------------------------------------------------------------------
) end of look-ahead
----------------------------------------------------------------------
( group and capture to \2:
----------------------------------------------------------------------
cat 'cat'
----------------------------------------------------------------------
| OR
----------------------------------------------------------------------
dog 'dog'
----------------------------------------------------------------------
) end of \2
----------------------------------------------------------------------
) end of grouping
----------------------------------------------------------------------