You can't just push a hash onto an array and then expect to extract it back out, you'll need to push a reference to the hash onto the array (and you'll definitely want to make sure %rec is a lexical hash inside your read loop by declaring with my()):

    my %rec = (state          => $part1[0],
               char           => $part1[1],
               stack_char     => $part1[2],
               new_state      => $part2[0],
               new_stack_char => $part2[1],
              );
    push(@db, \%rec);
[download]

Now, when accessing these, you'll need to dereference them:

foreach my $hash (@db){
    foreach my $key( keys %$hash){
        print "KEY: $key \n";
        print "VALUE: $hash->{$key} \n";
        print "________________________\n";
    } #end foreach $key
}#end foreach $hash
[download]

For further info on references and nested structures, check these perldocs: perlreftut, perlref, perllol, and perldsc.

update: Hmm, perlreftut doesn't seem to be included in the perlmonks perldocs, but if you have 5.00503 (I think that's when it got included) or later you can read it on your machine.