#!/bin/perl -w

# DFA SIMULATOR
# Michael S. Branicky, 1/23/1

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

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

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

# definition of s0
$s0=$Q[0];


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

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

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

# error-check F
print "\nFinal State(s): @F\n";
foreach $f (@F) {
  if (!inlist($f, @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
$s=$s0;

# 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: $s\n";
  print "Input character: $i\n";
  $key="$s,$i";
  $s=$delta{$key};
  print "     Next state: $s\n";
}

# report the result
if (inlist($s, @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;
}