#!/usr/bin/perl -w

# NFA SIMULATOR
# Michael S. Branicky, 1/31/1

#####################
# MACHINE DEFINITIONS
#####################
 
# definition of Q and Sigma
@Q = qw(1 2 3 4);
@Sigma = qw(0 1);

# definition of delta
%delta = qw(
  1,0 1
  1,1 1,2
  2,0 3
  3,1 4
);

# definition of F
@F = qw(4);

# definition of S
@S=qw(1);


################
# ERROR-CHECKING
################

# error-check S
print "\nInitial State Set: @S\n";
foreach $s (@S) {
  if (!inlist($s, @Q)) {
    print "ERROR: Invalid initial state.\n";
    exit(1);
  }
}

# error-check delta
print "\nTransition Function:\n";
foreach $key (keys (%delta)) {
  ($q, $i) = split(/,/, $key);
  @Nextq = split(/,/, $delta{$key});
  print "  delta( $q,$i ) = @Nextq\n";  # for debugging purposes
  if (!inlist($q, @Q)) {
    print "ERROR: Invalid delta (state).\n";
    exit(1);
  }
  if (!inlist($i, @Sigma)) {
    print "ERROR: Invalid delta (input).\n";
    exit(1);
  }
  foreach $nextq (@Nextq) {
    if (!inlist($nextq, @Q)) {
      print "ERROR: Invalid delta (range).\n";
      exit(1);
    }
  }
}

# error-check F
print "\nFinal State(s): @F\n";
foreach $q (@F) {
  if (!inlist($q, @Q)) {
    print "ERROR: Invalid final state.\n";
    exit(1);
  }
}


############
# SIMULATION
############

# get the input
print "\nInput:  ";
$inputstring=<STDIN>;
chomp($inputstring);
@inputchars=split(//,$inputstring);

# set the initial condition (by picking a random state in S)
srand( time() ^ ($$ + ($$ << 15)) );  # initialize the random number generator
$q=$S[rand(@S)];                      # cf. pages 57, 213

# operate on the input, character by character
foreach $i (@inputchars) {
  if (!inlist($i, @Sigma)) {
    print "ERROR: Invalid input character.\n";
    exit(1);
  }
  print "\n  Current state: $q\n";
  print "Input character: $i\n";
  $key="$q,$i";
  if (exists $delta{$key}) {
    @Nextq=split(/,/, $delta{$key});
  } else {
    print "\nCOMPUTATION DIED!\n\n";
    exit(1);
  }
  print " Next state set: @Nextq\n";
  # make a random choice from the next-state set (if not empty)
  if (@Nextq) {
    $q=$Nextq[rand(@Nextq)];
  } else {
    print "\nCOMPUTATION DIED!\n\n";
    exit(1);
  }
}

# report the result
if (inlist($q, @F)) { print "\nACCEPT.\n\n"; }
else { print "\nREJECT.\n\n"; }
exit(0);


###############################
# SUBROUTINE for list inclusion
#   Invoked: inlist ($target, @list)
#   Returns: 1, if $target is in @list; 0, o.w.
###############################
sub inlist {
  $target = shift @_;

  foreach $elt (@_) {
    return 1 if ($target eq $elt);
  }
  return 0;
}


###############################
# SUBROUTINE to sort and eliminate duplicate values from a list
#   Invoked: uniq (@list)
#   Returns: @uniq, the same list, sorted and w/duplicates removed
#   Sources: Christiansen and Torkington, _Perl_Cookbook_, p. 102
###############################
sub uniq {
  @list = sort(@_);

  @uniq = ();
  %seen = ();
  foreach $item (@list) {
    push(@uniq, $item) unless $seen{$item}++;
  }
  return @uniq;
}