TuringMachine.sc

enum HeadMovement{
  case Left, Right, Keep
}

type TuringMachineTransitionTable[BandElement, AlphabetElement, State] =
  Map[(State, BandElement), (State, AlphabetElement, HeadMovement)]

class InfiniteBand[BandElement, Alphabet](band:Map[Int, BandElement | Alphabet], 
      neutralElement: (BandElement | Alphabet)) {
  var pos = 0
  var currBand = band.filter(_ != neutralElement)

  def getElement(direction:HeadMovement) : (BandElement | Alphabet) = {
    pos += {
      direction match{
        case HeadMovement.Right => 1
        case HeadMovement.Left => -1
        case HeadMovement.Keep => 0
      }
    }
      
    if(currBand.contains(pos)){
      currBand(pos)
    }else{
      neutralElement
    } 
  }

  def updateBand(element:(BandElement | Alphabet)) = {
    element match {
      case `neutralElement` => if(currBand.contains(pos)){ currBand = currBand - pos }
      case _ => currBand = currBand.updated(pos, element)
    }
  }

  def asString() = {
    var res = ""
    if(currBand.nonEmpty){
      for(i <- 0 to currBand.keys.max) {
        val pos = i
        val element =
          if(currBand.contains(pos)){
            currBand(pos)
          }else{
            neutralElement
          }
        res = res + element.toString()
      }
    }
    res
  }
}

def simulateTuringMachine[BandElement, Alphabet, State] (table: TuringMachineTransitionTable[BandElement | Alphabet, Alphabet, State],
                                                  input: List[BandElement], initialState: State, neutralElement: BandElement)= {
  var done = false
  var currState = initialState
  var infiniteBand : InfiniteBand[BandElement, Alphabet] = new InfiniteBand(List.range(0, input.size).map(i => (i, input(i))).toMap, neutralElement)
  var currentDirection = HeadMovement.Keep
  while(!done){
    val element : (BandElement | Alphabet) = infiniteBand.getElement(currentDirection)
    if(table.contains(currState, element)){
      val (newState, newElement, direction) = table(currState, element)
      infiniteBand.updateBand(newElement)
      currentDirection = direction
      currState = newState
    }else{
      done = true
    }
  }
  (infiniteBand.asString(), currState)
}

enum Alphabet {
  case KerzeAus
  case KerzeAn
  case Kabel
  case Leer
}

enum Zustand {
  case q0, qK, q1, q2, q3, q4, q5
}

val band = {
  Alphabet.Leer ::
  Alphabet.Leer ::
  Alphabet.KerzeAus ::
  Alphabet.Kabel ::
  Alphabet.Leer ::
  Alphabet.KerzeAus ::
  Alphabet.Leer ::
  Alphabet.Leer ::
  Alphabet.KerzeAn ::
  Alphabet.Kabel ::
  Alphabet.Leer ::
  Alphabet.KerzeAn ::
  Alphabet.Leer ::
  Nil
}

val inputAsString =
  band.map(_.toString).mkString
     .replaceAll("KerzeAn", "i")
     .replaceAll("KerzeAus", "l")
     .replaceAll("Kabel", "-")
     .replaceAll("Leer", " ")

val table = (
    ((Zustand.q0, Alphabet.Leer), (Zustand.q0, Alphabet.Leer, HeadMovement.Right)) ::
    ((Zustand.q0, Alphabet.KerzeAn), (Zustand.qK, Alphabet.KerzeAn, HeadMovement.Right)) ::
    ((Zustand.q0, Alphabet.KerzeAus), (Zustand.qK, Alphabet.KerzeAn, HeadMovement.Right)) ::
    ((Zustand.qK, Alphabet.Kabel), (Zustand.q1, Alphabet.Kabel, HeadMovement.Right)) ::
    ((Zustand.qK, Alphabet.Leer), (Zustand.q1, Alphabet.Kabel, HeadMovement.Right)) ::
    ((Zustand.q1, Alphabet.Kabel), (Zustand.q2, Alphabet.Kabel, HeadMovement.Right)) ::
    ((Zustand.q1, Alphabet.Leer), (Zustand.q2, Alphabet.Kabel, HeadMovement.Right)) ::
    ((Zustand.q1, Alphabet.KerzeAus), (Zustand.qK, Alphabet.KerzeAn, HeadMovement.Right)) ::
    ((Zustand.q1, Alphabet.KerzeAn), (Zustand.qK, Alphabet.KerzeAn, HeadMovement.Right)) ::
    ((Zustand.q2, Alphabet.KerzeAus), (Zustand.qK, Alphabet.KerzeAn, HeadMovement.Right)) ::
    ((Zustand.q2, Alphabet.KerzeAn), (Zustand.qK, Alphabet.KerzeAn, HeadMovement.Right)) ::
    ((Zustand.q2, Alphabet.Leer), (Zustand.q3, Alphabet.Leer, HeadMovement.Left)) ::
    ((Zustand.q3, Alphabet.Kabel), (Zustand.q4, Alphabet.Leer, HeadMovement.Left)) ::
    ((Zustand.q4, Alphabet.Kabel), (Zustand.q5, Alphabet.Leer, HeadMovement.Left)) ::
    Nil
  ).toMap
val neutralElement = Alphabet.Leer
val initialState = Zustand.q0
var s = simulateTuringMachine(table, band, initialState, neutralElement)
var accepted = s._2 == Zustand.q5
var res = 
    s._1
     .replaceAll("KerzeAn", "i")
     .replaceAll("KerzeAus", "l")
     .replaceAll("Kabel", "-")
     .replaceAll("Leer", " ")