Because in the case of "dog:cat" =~ /(cat)*/;, the "*" quantifies the match to "zero or more" and the first match (at the leading "dog") is "cat" zero times.

Here's an illustration that beats to death that aspect of your issue.

#!/usr/bin/perl
use Modern::Perl;

my $str0 = "0 dog:cat" =~ /(cat)*/;
say "\$str0 $str0";                   # 1 -- original replaced by scal
+ar value

my $str1 = "1 dog:cat";
say "\$str1: $str1";
if ($str1 =~ /(cat)*/ ) {
    my $capture = $1;
    say "matched |$capture| in \$str1 ($str1) using * quantifier in re
+gex";  # see output: uninit $capture
}else{
    say "no match in \$str1 ($str1) using regex with * quantifier";
}

my $str2 = "2 dog:cat";
if ($str2 =~ /(cat)/ ) {
    my $capture = $1;
    say "matched |$capture| in \$str2 ($str2) using regex without quan
+tifier";
}else{
    say "no match in \$str2 ($str2) using regex without quantifier";
}

say "-" x10;

my $str3 = "3 cat:dog" =~ /(cat)/;
say "\$str3: $str3";                  # 1 -- original replaced by scal
+ar value

my $str4 = "4 cat:dog";
if ($str4 =~ /(cat)/ ) {
    my $capture = $1;
    say "matched |$capture| in \$str4 ($str4) using regex without quan
+tifier";
}else{
    say "fubar on |$str4| using regex without quantifier";
}

=head

$str0 1
$str1: 1 dog:cat
Use of uninitialized value $capture in concatenation (.) or string at 
+F:\_wo\junk20111109.pl line 11.
matched || in $str1 (1 dog:cat) using * quantifier in regex
matched |cat| in $str2 (2 dog:cat) using regex without quantifier
----------
$str3: 1
matched |cat| in $str4 (4 cat:dog) using regex without quantifier

=cut
[download]

(This in no way deprecates choroba's discussion but is offered in the hope that the simpler example here may be more accessible).