(A) --B--> (C) --1--> (R) --L--> (F)
(A) --D--> (D) --2--> (Q) --3--> (F)
(A) --P--> (M) --4--> (P) --9--> (F)
[download]

<fsm initial_state="A" final_state="F">

<delta><start>A</start><input>B</input><rest>C</rest></delta>
<delta><start>C</start><input>1</input><rest>R</rest></delta>
<delta><start>R</start><input>L</input><rest>F</rest></delta>


<delta><start>A</start><input>P</input><rest>M</rest></delta>
<delta><start>M</start><input>4</input><rest>P</rest></delta>
<delta><start>P</start><input>9</input><rest>F</rest></delta>

<delta><start>A</start><input>Q</input><rest>D</rest></delta>
<delta><start>D</start><input>2</input><rest>Q</rest></delta>
<delta><start>Q</start><input>3</input><rest>F</rest></delta>



</fsm>
[download]

use XML::Twig;

my $twig  = XML::Twig->new;

my @input = qw(Q 2 3);

$twig->parsefile("fsa.xml");
my $root = $twig->root;
my $I = $root->att('initial_state');
my $F = $root->att('final_state');

my @delta = $root->children;

sub bfs {
    my ($type, $search_text, @nodes) = @_;
    grep { $_->first_child($type)->text eq $search_text } @nodes ;
}

my @start_candidate = bfs('start', 'A', @delta);

&DFS(\@start_candidate,\@input);

sub DFS {
    my ($start_candidate,$input) = @_;

    for my $path (@$start_candidate) {
        my $current_position = $path->next_elt('start')->text;
        warn "currently at: $current_position";
        return 1 if $F eq $current_position and !@$input;
        my @input = @$input;
        if ($path->next_elt('input')->text eq shift(@input)) {
            my $next = $path->next_elt('rest');
            my @new_paths = bfs('start', $next->text, @delta);
            return DFS(\@new_paths, \@input);
        } else {
            next;
        }
    }
    return 0;
}
[download]