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;
}