my %cfg = (
  S => [qw/aB bA/],
  A => [qw/aS bAA a/],
  B => [qw/bS aBB b/]
);

my $string = 'S';
my $regex  = join "|" => keys %cfg;

print "$string\n"
    while $string =~ s/($regex)/ $cfg{$1}[ rand @{$cfg{$1}} ] /e;

print "$string\n";