For the 9 cases, I would simply enumerate them:

/(
 (0[a-z]1)
|(1[a-z]2)
|(2[a-z]3)
|(3[a-z]4)
|(4[a-z]5)
|(5[a-z]6)
|(6[a-z]7)
|(7[a-z]8)
|(8[a-z]9)
)/x
[download]

For further experimentation, I would write a test rig like the following to easily play with regular expressions and data and see how things work:

#!perl
use 5.020;
use Test2::V0 '-no_srand' => 1;

my @cases = (
    # case, expected result, todo text
    ['13s4', '3s4' ],
    ['3s44', '3s4' ],
    ['0a1', '0a1' ],
    ['0a2', undef ],
);

for my $case (@cases) {
    my( $line, $expected, $todo ) = @$case;
    my ($result) = $line =~ /(
                           (0[a-z]1)
                          |(1[a-z]2)
                          |(2[a-z]3)
                          |(3[a-z]4)
                          |(4[a-z]5)
                          |(5[a-z]6)
                          |(6[a-z]7)
                          |(7[a-z]8)
                          |(8[a-z]9)
                          )/x;

    my $t; if ($todo){ $t = todo( $todo ) };
    is( $result, $expected, $line );
}

done_testing;
[download]