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]

Which can be shortened to

my $regex = join '|', map $_ . '[a-z]' . ($_ + 1), 0 .. 8;
...
    my ($result) = $line =~ /($regex)/;
[download]

map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]

Not elegant, but fits the spec:

/0.1|1.2|2.3|3.4|4.5|5.6|6.7|7.8|8.9|9.0/
[download]

Thanks for your answers.

Does this mean, arithmetic is not possible, in this case I have to generate a list of all possible cases ?

You can run Perl code inside a regular expression (see perlre):

#!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 =~ /
    (
      (\d).(\d)   # Capture the stuff
      (?(?{ $2+1 != $3 })(*FAIL)) # decide if things match our extende
+d criteria
    )/x;

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

done_testing;
[download]