beaver4.groovy

new Machine().with {
  states = ['A','B','C','D','H']
  accept = ['H']
  initialState = 'A'
  sigma = ['1']
  blank = '0'
  gamma = sigma + blank
  transitions['A']['0'] = [write: '1', move: 'R', newState: 'B']
  transitions['A']['1'] = [write: '1', move: 'L', newState: 'B']
  transitions['B']['0'] = [write: '1', move: 'L', newState: 'A']
  transitions['B']['1'] = [write: '0', move: 'L', newState: 'C']
  transitions['C']['0'] = [write: '1', move: 'R', newState: 'H']
  transitions['C']['1'] = [write: '1', move: 'L', newState: 'D']
  transitions['D']['0'] = [write: '1', move: 'R', newState: 'D']
  transitions['D']['1'] = [write: '0', move: 'R', newState: 'A']
  validate()
  accepts '0'
}

beaver5.groovy

new Machine().with {
  states = ['A','B','C','D','E','H']
  accept = ['H']
  initialState = 'A'
  sigma = ['1']
  blank = '0'
  gamma = sigma + blank
  transitions['A']['0'] = [write: '1', move: 'R', newState: 'B']
  transitions['A']['1'] = [write: '1', move: 'L', newState: 'C']
  transitions['B']['0'] = [write: '1', move: 'R', newState: 'C']
  transitions['B']['1'] = [write: '1', move: 'R', newState: 'B']
  transitions['C']['0'] = [write: '1', move: 'R', newState: 'D']
  transitions['C']['1'] = [write: '0', move: 'L', newState: 'E']
  transitions['D']['0'] = [write: '1', move: 'L', newState: 'A']
  transitions['D']['1'] = [write: '1', move: 'L', newState: 'D']
  transitions['E']['0'] = [write: '1', move: 'R', newState: 'H']
  transitions['E']['1'] = [write: '0', move: 'L', newState: 'A']

  validate()
  new File('out-beaver-5.txt').withWriter {writer->
    accepts '0', {writer.println it}
  }
  println()
}

Machine.groovy

class Machine {
  def states, accept, initialState, sigma, blank, gamma
  def transitions = [:].withDefault{[:]}

  def validate() {
    def actions = transitions.values()*.values()
    def usedchars = transitions.values()*.keySet().sum() + actions.write.sum()
    assert states.containsAll(transitions.keySet() + actions.newState.sum()),
      "transitions should only contain known states"
    assert states.containsAll(accept),
      "the accepting states should be already known states"
    assert initialState in states,
      "the initial state should be an already known state"
    assert gamma.containsAll(sigma),
      "the language of the machine should be included in the tape"
    assert blank && (blank in gamma) && !(blank in sigma),
      "there should be a blank character"
    assert gamma.containsAll(usedchars),
      "transitions should only contain known characters"
    assert ['L', 'R'].containsAll(actions.move.sum()),
      "moves should be limited to left or right"
    this
  }

  def stateAfter(tapeString, steps, printer={println it}) {
    newInstance(tapeString, printer).stateAfter steps
  }
  def accepts(tapeString, printer={println it}) {
    newInstance(tapeString, printer).accepts()
  }

  def newInstance(tapeString, thePrinter) {
    def tapeContents = (tapeString.chars)*.toString() as List
    assert gamma.containsAll(tapeContents),
      "the tape contains unknown characters"
    new MachineInstance().with {
      machine = this
      printer = thePrinter
      currentState = initialState
      tape = new Tape(head: 0, blank: machine.blank, data: tapeContents)
      it
    }
  }
}

MachineInstance.groovy

class MachineInstance {
  def machine, tape, currentState, printer

  def stateAfter(steps) {
    while (hasTransition() && steps--) {
      applyTransition currentTransition()
    }
  }
  def accepts() {
    while (hasTransition()) {
      applyTransition currentTransition()
    }
    machine.accept.contains currentState
  }
  def currentTransition() {
    machine.transitions[currentState][tape.read()]
  }
  def hasTransition() {
    report()
    currentTransition() != null
  }
  def applyTransition(transition) {
    currentState = transition.newState
    tape.write transition.write
    tape.move transition.move
  }
  def report() {
    if (currentTransition()) {
      def t = currentTransition()
      printer "$currentState -> $t.newState ($t.write, $t.move) $tape"
    } else {
      printer "$currentState: halting ::: $tape"
    }
  }
}

Tape.groovy

class Tape {
  def head, data, blank

  def hasData() {
    0 <= head && head < data.size()
  }
  def read() {
    data[head]
  }
  def write(character) {
    data[head] = character
  }
  def move(direction) {
    direction == "R" ? head++ : head--
    adjust()
  }
  def adjust() {
    if (head == -1) {
      data.add 0, blank
      head = 0
    } else if (head == data.size()) {
      data.add blank
    }
  }
  String toString() {
    (data[0..<head]*.center(3).join()
      + '['+data[head]+']'
      + data[(head+1)..<data.size()]*.center(3).join())
  }
}

task1.groovy

new Machine().with {
  states = ['q0', 'q1']
  accept = ['q0']
  initialState = 'q0'
  sigma = ['1','0']
  blank = ' '
  gamma = sigma + blank
  transitions['q0']['1'] = [write: '1', move: 'R', newState: 'q1']
  transitions['q0']['0'] = [write: '0', move: 'R', newState: 'q0']
  transitions['q1']['1'] = [write: '1', move: 'R', newState: 'q0']
  transitions['q1']['0'] = [write: '0', move: 'R', newState: 'q1']
  validate()

  assert accepts('0101')
  assert !accepts('01011')
  assert !accepts('01 11')
  assert accepts('11 11')
  println()

}

task2a.groovy

new Machine().with {
  states = ['q0', 'q1', 'q2', 'q3']
  accept = []
  initialState = 'q0'
  sigma = ['0','1','2']
  blank = 'B'
  gamma = sigma + blank
  transitions['q0']['1'] = [newState: 'q0', write: '1', move: 'R']
  transitions['q0']['2'] = [newState: 'q1', write: 'B', move: 'L']
  transitions['q1']['1'] = [newState: 'q1', write: 'B', move: 'R']
  transitions['q2']['0'] = [newState: 'q0', write: '0', move: 'R']

  transitions['q0']['0'] = [newState: 'q0', write: '0', move: 'R']
  transitions['q1']['0'] = [newState: 'q0', write: '1', move: 'L']
  transitions['q1']['2'] = [newState: 'q1', write: '2', move: 'R']
  transitions['q2']['B'] = [newState: 'q2', write: '1', move: 'L']

  transitions['q0']['B'] = [newState: 'q1', write: 'B', move: 'L']
  transitions['q1']['B'] = [newState: 'q2', write: 'B', move: 'R']
  transitions['q2']['1'] = [newState: 'q1', write: '2', move: 'R']
  transitions['q2']['2'] = [newState: 'q3', write: '0', move: 'L']
  validate()

  accepts '01012000'
  println()
}

task2b.groovy

new Machine().with {
  states = ['q0', 'q1', 'q2']
  accept = []
  initialState = 'q0'
  sigma = ['0','1','2']
  blank = 'B'
  gamma = sigma + blank
  transitions['q0']['1'] = [newState: 'q0', write: '1', move: 'R']
  transitions['q0']['2'] = [newState: 'q1', write: 'B', move: 'L']
  transitions['q1']['1'] = [newState: 'q1', write: 'B', move: 'R']
  transitions['q2']['0'] = [newState: 'q0', write: '0', move: 'R']

  transitions['q0']['0'] = [newState: 'q0', write: '0', move: 'R']
  transitions['q1']['0'] = [newState: 'q0', write: '1', move: 'L']
  transitions['q1']['2'] = [newState: 'q1', write: '2', move: 'R']
  transitions['q2']['B'] = [newState: 'q2', write: '1', move: 'L']

  transitions['q0']['B'] = [newState: 'q1', write: 'B', move: 'L']
  transitions['q1']['B'] = [newState: 'q2', write: 'B', move: 'R']
  transitions['q2']['1'] = [newState: 'q1', write: '2', move: 'R']
  transitions['q2']['2'] = [newState: 'q1', write: '0', move: 'L']
  validate()

  stateAfter '01012000', 67
  println()
}