"... if a new regex given is already covered by another ..."

You left this requirement open to ambiguous interpretation. Do you want an exact match or do you want fuzzy matching? For example: abc.*f will match all the things that abc\wf will match, but not vice versa. So if abc.*f is already issued and the user tries to issue abc\wf, should your program issue a warning?

In the off-change that it should not ... then all you need to is store each submitted value from user input into a hash as a key and increment the value for that key each time the key is seen:

my %seen;
while (chomp(my $input = <STDIN>)) {
    exit unless $input;
    $seen{$input}++;
    warn "you already issued $input\n" if $seen{$input} > 1;
    print "issued: ", join(', ', sort keys %seen ) ,$/;
}
[download]

If this is correct, then the fact that you are storing regular expressions is misleading -- you really just want to store strings that will be used as regular expressions later. Please clarify. :)

L-LL-L--L-LL-L--L-LL-L--
-R--R-RR-R--R-RR-R--R-RR
B--B--B--B--B--B--B--B--
H---H---H---H---H---H---
(the triplet paradiddle with high-hat)