Since you mentioned DFA with regex (which reminded me of natural language processing), here's a naive twisted example:

use Tie::RegexpHash;
use Regexp::Subst::Parallel;
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
my $how = sub {
    my %ans = (
        is => "print \"It's fine.\\n\"",
        are => "howare(\"$_[3]\")"
    );
    eval $ans{$_[2]} ;
};

sub howare {
    tie my %ans, 'Tie::RegexpHash';
    %ans = (
        qr/you/i           => "print \"I'm fine.\\n\"",
        qr/^(?!you)(.*)$/i => "print \"All good.\\n\""
    );    
    eval $ans{$_[0]} ;
}
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
my @sr =(      
    qr/^(how) (is|are) (you|.*)(\?)$/i => $how,
    qr/^(?!how)(.*)$/i                 => sub{print "Say what?\n"}
);
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
$_ = "\nHow is everything?\n"; print; 
subst($_, @sr);

$_ = "\nHow are you?\n"; print; 
subst($_, @sr);

$_ = "\nHow are things?\n"; print; 
subst($_, @sr);

$_ = "\nDo you dig me?\n"; print; 
subst($_, @sr);


__END__

How is everything?
It's fine.

How are you?
I'm fine.

How are things?
All good.

Do you dig me?
Say what?
[download]