@observation = qw(empty a a empty);

$trans = { 'end' => {M2 => 1},
 	  'M2' => { I1 => 0.1, M1 => 0.3},
          'I1' => { begin => 0.8},
	  'M1' => { begin => 0.2},     };


sub viterbi {

my $state = shift;
my $output = shift;


# V (begin)(0) =1; V(anyother)(0) =0; V(begin)(other_numbers) =0;



if($state eq begin) { if($output == 0) { return 1;} else { return 0; }     }

elsif ( ($state ne begin) && ($output == 0) ) {return 0; }

else 

{  

  $r=$output-1; 
   
#maximum of below foreach#
            
 foreach my $yy ( keys %{$trans->{$state}} ) 

 {  $trans->{$state}->{$yy}  *  viterbi($yy, $r) ;  }    

}
}
print "\n\n", viterbi(end, 3);